Prelude.io has fiat/bc and btc/bc, they're pursuing full finCEN compliance and are registered in Wyoming. A Coinbase type service might not be as far away as you guys think. Moolah will be putting out ATMs soon as well, so if we have enough volume on Prelude, it's likely we'll be on their ATMs as well.
I did just use
http://www.virwox.com successfully. You have to buy some linden dollars, which fast transfer to bitcoin. You get the current rate then it takes 48hrs (seems long) to get to you for a new customer. It's not fast to receive your coin, there's the normal fee but it felt fast and safe. They have different fiat options.
Prelude could be great. But the options are really tricky and limited for people.