My local shop does the following for $40:
* Derailleur Adjustment
* Brake Adjutment
* Wheel Truing
* Lube Chain
* Lube Suspension Fork
* Minor Cleaning
I've never had them work on my bike, but I've refered many folks to the shop and they've been consistantly happy. The one odd thing about that shop is they charge a small fortune to replace brake and derailluer cables and housings. I think that's like another $40 for just basic cables which I could understand if you weren't already having the cables adjusted...
I have a local guy that used to work as a mech at another shop and for $20, he adjusts brakes and derailleurs, trues the wheels, lubes pretty much everything. So I save $20 and I have to clean it myself.