Assuming all transactions will go to one address or come from "traceable" sender addresses is a bit presumptive.
Why not let the users sign up for the service (over Tor or whatever), then generate a bitcoin address for them to send BTC to? Then every transaction has a new address.
Besides that, there are a ton of ways to keep it anonymous using bitcoin.
You could buy BTC with cash of course, but then why not just send the cash direct?
I suppose you could also use washers but I'm not sure how reliable those are.
..I guess what I'm saying is that, lo and behold, Bitcoin might actually eventually work as an 'exchanger asset'; I've already discussed with a friend in the UK the possibility / advantages of using BTC to send cash [1] to them (bank transfer from this place would cost >= 15 pounds otherwise). They could then use a UK-based BTC exchanger, or -- find a local bitcoin trader (and yes there are some)!
(Also see: [2]) :)
Just saying!
In any case, I root for SDF, Godspeed you awesome people.
[1] Well, effectively cash: if both of us were to use local miners/traders, I would be effectively depositing cash, and my friend would be taking the cash out of the system. (See illustration in [2]) The process could be further abstracted away if my wallet were set up to automatically send all incoming coins to a pre-specified address; that address could my friend's trader's address where they would be sitting, sipping tea and waiting for the incoming coins, or (if my friend were not to care about anonymity at all) an exchanger's address; the exchanger could be set up to automatically make a local wire transfer (so free / very cheap) to a local UK bank account upon incoming coins; et cetera, et cetera.
[2] http://en.wikipedia.org/wiki/Hawala ; & a simple image: http://en.wikipedia.org/wiki/File:Hawala.png
edit expanded footnote1, etc.