I'm not shocked you had a hard time getting through to an Apple Store the day after the iPhone 4 launch; all the people looking for phones are likely calling non-stop to find out if they have any in stock.
I know in this area (NJ) the Apple Stores have some in stock, but not all memory sizes & wireless options. I suspect the same will be true down there.
Alternate option: National electronics chain Best Buy is also selling the iPad in the US, and from their website they'll let you check stock for the various stores. Between the Best Buy option and being able to call Apple Stores once iPhone fever subsides, I think you should be ok getting one here.
Enjoy your trip to the States. Not sure I'd pick Austin to visit in July, but...