This happened to me sometime last year. Similar situation, in that I just happened to take a look at my American Express statement online one night and saw two transactions that I didn't make. Each was for about $30 or $40 to a couple different online merchants (McAfee and AOL.) I guess their theory is they do small to medium-sized transactions in the hopes that they don't get noticed. Well, I noticed, and they issued me a new card and investigated the transactions. They disappeared from my account by the time my next statement rolled around, so I was happy.

Not sure if the source of the theft was online or dumpster-diving a receipt, but I guess this sort of thing happens a lot. I know of six or seven other friends/acquaintances who've had card numbers stolen.

Best of luck resolving things in a timely manner.