I've done this twice now, and both times is was fast and easy.
You make a "reservation" to deposit after you login to exhangebitcoins.com. You choose the bank and enter the amount. Then you get a page with instructions, which I printed out and brought to the bank with me.
I made my cash deposit at the bank, filling out the deposit slip as instructed on the printout I had.
I got a receipt from the teller.
I went to lunch. I took a picture of the receipt with my phone, and emailed it to them as specified in the instructions. I did this while I was waiting for my food.
By the time I got back to the office, I had an email stating my deposit was confirmed. I logged in and there it was. I placed a buy order.
The only complaint I have at all is the volume on exhangebitcoins.com is pretty low, so trades can take several hours to complete if you are not willing to match the lowest ask, which in my two experiences has been somewhat higher than the going rate at MtGox at the time. For example, today I paid $6.1 / BTC when MtGox was at 5.94.
That said, it is THE fastest and easiest way to get bitcoins for cash, on a weekday in the USA at least.