Same problem in Houston. Just re-sodded half of the back yard. Liesl's puppy antics, digging, peeing, etc. killed it all last year.
She has calmed down significantly now, and we are training her not to dig holes. I think the sod will work, but I view it kind of like owning a golf course--you'll have to watch it on a daily basis, fertilize, water, and fix holes asap.
We never could get a good cover from seed because it took too long to grow and was too thin when it did. So, I recommend you try Augustine sod.
Liesl, b. 1/1/11