And with the transaction history included, and most transactions, by necessity, tell something about you (at least the merchant probably needs to know where to send your item or whatever) it seems to me that it would be utterly trivial to get a hold of the real identity of the vast majority of the users after even his/hers first transactions. And this is valuable information and it will, as today, be bought and sold freely - maintaining a database of who is who seems like childs play. Not only that, but also who bought what (or at least from who), making it the least anonymous way to make a purchase imaginable (almost as bad as saying what you bought on twitter).

For anyone hoping of using bitcoins for their everyday transactions, would that be any more anonymous than a credit card is today? Or even worse, it might give you the sense that you are anonymous when you are not.

True, pseudonymous is the right word. You can start mining bitcoins without disclosing any personally identifiable information (if you obscure your IP address or connect from a public wifi network or something), you could buy bitcoins from someone on craigslist, pay in cash and have them sent to this account, etc. But the minute you make a transaction that links this account to you, all the activity on the account is linked to you. At least that's how I understand it, see [1]

[1] https://en.bitcoin.it/wiki/Anonymity#Staying_Anonymous