westlakers, there's only two things I can think of, based on what we know from this thread, that might be the culprit....
1. Do you by some chance have any discount codes applied to your account? That usually plays hell with getting things done unless you go to a Corporate Store, because regular stores cannot make certain changes to corporate accounts (or so I have been informed by AT&T). Once a code like that is on your account, it's moved into a different type of account. It's one of the reasons a lot of people got screwed on Day 1, because Apple Stores and even regular AT&T stores couldn't do any upgrades on those accounts.
2. I think maybe the issue actually lies with your wife's account. From what I can tell (though it isn't clear), you bought your 3G iPhone on 2/28 (which should make you eligible), but at some point after that put her on your account which might be the issue. If you had to change your plan over from a regular plan to a familytalk plan, or if you just added the line to it, might have either been incorrectly done or marked on the account in such a way that it comes up as you being on a "new 2 year contract" which might trigger them into not seeing you as eligible.
Either way, based on everything in the thread you darn well should be eligible. I don't know if this would help or not, but I would actually give Apple a call. They have a separate department to handle issues with the iPhone, and they might be able to help.I know it sounds weird, but I had some account issues with my 3G iPhone when I purchased it and pretty much got nowhere with AT&T. After about three days of frustration, I called up Apple, and the CSR got AT&T on the phone and helped get everything resolved to my satisfaction.