Where can I buy bitcoins with an American Express gift card?
http://btcquick.com uses Google Checkout and supports Amex, I have not tried a gift card but it should work.

They do require identity verification to combat the (massive) fraud risk they face.