I just wanted to rep the London Bicycle Workshop on Theobald's road (who must be less than 2 years old so they sort of fit in this thread). The mechanics in there are very good, knowledgable and sort of hilariously gruff and enourmously helpful at the same time. They've sorted out some strange problems and been honest about price. They also don't have a six-week wait for a tune-up unlike another bike shop near Gary's Inn Road...
+1, Great workshop. They know what they're talking about, and are keen to help. Service prices are competitive too.