I just brought my X1900, too. I was NOT about to lug my Mac Pro to the Apple Store even if I still had it. That's ridiculous.
I thought so too. The genius told me he wanted to test the system to make sure the video card was removed and installed properly, but I think any average user could remove the card easily. You don't even need a screwdriver. Just remember to push on the release clip at the end of the card slot before you try pulling the card. I work near the Pasadena store and I have had a couple of experiences there where the store employees were a little confused (to put it politely). I live near the Glendale store and have never had problems there.
I picked up my replacement nvidia 8800GT today. No phone call, but I dropped by just in case it came in this morning and it had. Two days is pretty good turn around time. I got a receipt which says the 8800GT costs ~$520.00