Is it possible for a decentralized currency to have untraceable transactions?
You are quite right that there are some drawbacks to reusing a bitcoin address, while at the same time it can be inconvenient to generate a new address each time. 

I think you'll find its not possible to make an untraceable payment system where the money supply is limited. If money creation is controlled (as with bitcoin), nodes need a way to trace the money back to a valid origin.

As for the limitations of bitcoin, read on.

You might be interested in BIP 21 (Bitcoin Improvement Proposal 21), which is an official URI extension which bitcoin clients or wallets can use to make payments easier. Basically a seller can present a bitcoin URI (i.e. a link) to the buyer, and if the buyer's bitcoin client is compatible, the bitcoin client shows a payment screen saying e.g., "Would you like to send Bob 20 bitcoins?". What you should note is the seller can put any bitcoin address in the URI, meaning if most bitcoin clients + sellers supported this scheme, many transactions could easily use one-off bitcoin addresses, which helps achieve the privacy you're after. 

Note there is still the problem that in can be tricky to send bitcoins to e.g. a friend, and that like you said, being able to 'discover' someones bitcoin address by using e.g. their email address would be handy. I have a side project Bitcoin Payment Service which attempts to solve that problem. Basically its an open-source web app that allows anyone to initiate a bitcoin payment to the web site's owner. You can check out a demo of BPS.