In Nepal ride as far as the Tibetan border then bus it with all your gear back to Khatmandu. Book yourself on one of the tourist jeeps to Lhasa, and either get off just over the border (if possible) or take another ride back to the border from Lhasa and continue cycling.
Bit fiddly but at least it'd allow you to keep the overland momentum going. Any reason why it wouldn't work?

any reason why it wouldn't work? No - and Yes - because all of the jeep and air tours from KTM enter on group visas. That means that you have to leave on the same visa. I do know someone that took a jeep to Lhasa with his bike from KTM - ditched the group and then exited back to KTM overland by bike, but he had a lot of problems exiting because the other person on his group visa had already left the country - too ill to continue cycling. It was a good thing that back in his home coumntry, he was sleeping with the president of the country's Chinese friendship association and he had some letters of introduction and the ability to bully officials around a bit. So you could try it.

Also I believe the group Visa's are pretty short 15/30 days, and can't be extended (or is prohibitively difficult to do so). Note that it's pretty darned difficult to extend in Tibet.
Lhasa PSB sometimes gives 7 days extension , sometimes not-no rhyme nor reason to it.
Shigatse PSB gave me 10 days extension, but it took some extra extra polite conversation-as well as waiting untill only 7 days left on the current Visa extension (extended 30 days in Kashgar). Shigatze PSB also requires folks to go through an Agency-which really doesn't do anything other than walk over to the PSB with forms you allready filled out. Costs twice as much for all there "hard work".
-Carefull- If you allready have a Chinese Visa, say one you got from home, and you decide to enter from Nepal, your original Visa will be cancelled.
Happened to a Brittish guy I meet last week who had a super nice 6 month visa (yes a 6 month visa-I had never heard of one either), It was cancelled. Stamped rite acrossed it.
~Cheers from Kathmandu!~

Is that right Rainboy? I understood that once you're in on one of these 'group' visas you can basically do as you please. I never heard you'd need to leave together as well...

There's another very good reason not to take that route. It gains height very quickly with nowhere to stay - or even to camp on the way. You'd have serious problems with altitude sickness.

Not a ride for first-timers, granted, but doable I think.
The starting point (Nepalese border) is at 2400m. Certainly possible to spend a night in Nyalam (3700m) on the way up to the pass (5000m). If you'd recently spent some time at high altitude these two steps wouldn't be a problem. It'd be a good idea to have done a high altitude treck in Nepal just before setting off.
Otherwise, it could be done in smaller steps, camping once between the border and Nyalam, and again between Nyalam and the top. It's always possible to camp if you've got approporate gear (bivvy bag/ tent with rock pegs and a hammer)
This site's great for altitudes/ accomodation/ etc

From what I've read, even camping like that isn't an option on that road, and altitude sickness hits everyone - however much experience/fitness you've got.
I've done enough riding at altitude to know that I'd get into real trouble on that road. It would be easier if you've recently spent time at altitude - but the effect of that only lasts a week or so.
Most people would probably be OK as far as Nyalam but after that 300m a day of extra ascent would be a safe limit - and make for a grim week.
"in theory" - you're supposed to leave together - its a "group" visa, but as I said above, there are exceptions as in the case of my friend. And just to confuse things more - supposedly(according to Camel), you are not supposed to get individual alien travel permits in Shigatse - but I did - by myself - just walked in and filled out the form and got one. I said I was travelling with some people but they were behind me and coming in tomorrow or the day after. But getting that piece of paper was a waste of money - Nobody asked to see it - not once on the rest of my trip through to KTM.
I'm not sure what pq is saying in post #6 - you can camp almost anywhere - I don;t think you want to do it too close to towns, but I camped when I was in between towns the whole way.
Matt, the starting point isn't at 2400 metres, the border is a long way up the road. Kathmandu is about 1400 metres, and Dolalghat Village (the end point of the big descent down from Nyalam) is at just 600 metres AOD. So you will need some acclimatisation just to get to the border. You are really talking of over 4,000 metres of climbing in just 170 or so km. So whichever way you look at it, there is a massive altitude gain and it would be very difficult to do it without going beyond what is advised by all the medical authorities i've read (i.e. 300 metres per day). And being tough and experienced has little to do with it - ADD can strike even the most experienced. In Manali in India this year I met a guy who very nearly died of ADD when going on a mountain biking trip to the Spiti Valley - he had been to altitude numerous times, and was extremely fit. It just hit him out of the blue as a result of going from Delhi, then Manali, then cycling up the Rohtang Pass and beyond too quickly.
I've no idea how those cyclists who have done Kathmandu to Lhasa have done it. I suspect most have taken a tour bus up to Nyalam and set off from there. I don't think there is any way a solo traveller on a bike will be allowed cross the border on the main road, its just not done. Also, there is a checkpoint just outside Nyalam, I don't think they will let cyclists pass if going the 'wrong' direction. I also suspect that things might tighten up a little as we get closer to the Beijing Olympics.
I can't remember the details, but didn't someone suggest here a while ago that there was a possible illegal but doable crossing point on a track used to go direct from Mt. Kailash to Nepal? That might be worth looking into if you are feeling particularly adventurous.
Btw, matt, in answer to your last post below about heavy duty rims, I'd add to your list the Rigida Sputnik. This months Cycling Plus magazine rated a wheel with a Sputnik rim and Deore hubs built by Spa Cycles in the UK as their 'value pick of the year' for touring wheels.

Thanks for all your input, particularly regarding safety. Incidentally I'm at home for the moment (sigh) and if I attempt this it won't be until later next year.
At what altitude does the '300m rule' come into play? I'd be interested to hear what other people think about this, but from my own experience (and the half a dozen or so cyclists I've travelled with and spoken to en route), the very early symptoms of altitude sickness (slight headache, slight dizziness) haven't arrived until between 2500 and 3000 metres, climbing from a starting point of around 1000 metres in two days. Personally, I wouldn't think twice about doing the same again. Again, It'd be good to get further views on this.
It would certainly be a long drawn out ride but I'm convinced it's physically doable (you're crossing the Himalayas the wrong way for Christ's sake I'd be annoyed if it was easy!) Thinking through the time that'd be needed:
Certainly if you've spent any time in Khatmandu (1300m) you could ride to the NEPALESE side of the border (1800m-113km) in two days.
Perhaps cross the border the next day and spend the rest of it aclimatising in Zhangmu (2300m).
Next, I personally wouldn't be too worried about continuing to 3000 metres, before slowing down to 300 metre climbs the following two days, arriving at Nyalam (3760m). That's 31 km in three days! Plenty of time to admire the view.
You'd need a further four days at this 'safe' rate of ascent to get over the top- and from the description in the site I linked above there are several road repair stations and villages along the way, so you wouldn't even have to camp (assuming they're all still there). 215kms, 8 days. Could be worse. In fact sitting here in my living room I can't think of anything more appealing than cycling over the Himalayas the wrong way...
Is the checkpoint near Nyalam the only one likely to give you problems? Any hope of sneaking through at night? If it came to it you could get dropped off just past it (having already cycled from KTM to the border and back in Nepal). It'd mean 40kms not cycled. Still, better than flying to Singapore...