Steels is a good shout.
The Hub on Quayside may also be able to help out.
Can't say a bad word about Start - I've bought a bike, had one serviced, and a friend has had a bike built by them; reasonablely priced and knowledgeable chaps. Maybe not the best bet for older bikes though.
There's also Cycle Centre on Shields Road - had an excellent service from them too.
Slightly out of town is Cycle Logical who are good.
Recyk'ybike are OK, but they can be quite expensive in my experience.
When they get back on their feet, KB Cycles is an excellent shop, one of the oldest around I believe.