I have owned my TCH for a mere 2 days, but on taking delivery I had one of the fobs in the car and was using the other to try and open the door and it would not work, though the car would still start (the extra fob was in the backseat however). It took me a while to realize that the interference I was getting was from my own fab, rather than from an external source. When I removed the extra fob from the vicinity all was well.

You mentioned that "your wife tried to start it with her fob." Were both of you there with your fobs the whole time with the starter/locking issue by that store? Could that have possibly been the problem?

-Jake