Like the guy above said, the store will have to run tests to make sure it's the phone and not crappy AT&T service in your area.
As far as the color switch, it couldn't hurt to ask. Since you already have a 16GB they might be willing if it's in stock.