A recent update:
There's now a 'Tampopo' in the 'Triangle' shopping centre by Victoria station. It has exactly the same menu as the other one, and the early evening menu (£6.95 for a starter and main course if you eat before 7pm) has one starter and two main options that are vegan. It's good value, and the staff are approachable. A good place to take kids, as they have high chairs, colouring sets etc. Its a pity they don't do fruit juice, as I often fancy a change from green tea.
'Ning' is a Malaysian restaurant at the top of Oldham St that has a sign in the window saying 'Vegan and vegetarian friendly'. I've had takeaway green curry from there a few times and it is gorgeous. Haven't got round to having a sit down-meal there yet.
I went in '8th Day' cafe for the first time in nearly a year, and was disappointed. The woman serving was very slow, and it took ages for her to acknowledge that I was there. They have also taken those wonderful pizzas off the menu

it remains a very ethical place, though.
'Earth Cafe' has now dropped their organic stance and focuses on locally sourced produce. They have lowered their prices and improved the range of options.
'Cafe Pop' is a really good place to get vegan sosages. They do bangers and mash for £3.95 with loads of gravy and big fat sosages. They also do cheap sosage toasties. An atmospheric, friendly place. Unfortunately they charge extra for soya milk, and still don't have any vegan cakes.
'Herbivore' still doesn't do vegan main course options, though I'm told the soups are usually a safe bet.