Time to call in a favour

This one has me a little stumped so it's over to Mr RG for a little advice
I have a work Levono laptop, bottom of the range model, but useful for keeping in contact while away on trips. Over the years, I have successfully been able to tether a mobile phone to it for internet access.
Recently, I upgraded it to Ubuntu 9.10, and the tethering between it and the WinMobile based phone stopped working - I was using usb_rndis_lite driver with the previous 9.04. A couple of 'fixes' have been suggested in the Ubuntu forums, but they don't seem to work in this case.
Anyway I remember reading about an app that could turn your phone into a wireless hotspot, and also hear that our own RG also uses this method of tethering. After poking around the interwebs a bit, I settled on a commercial program called
WMWifiRouter. I fired this up and got it connected to an eeepc netbook no problems. The eeepc was the guinea pig because it is my geek tool of choice for an upcoming bike ride in Victoria. eeepc runs Ubuntu netbook remix 9.04
Satisfied with the excellence of the product, my attention turned to getting the work laptop connected. Of course it just won't happen. The phone will connect to every other computer in the house, and a friends iPhone. It will even connect to the laptop in question if I boot the Windoze OS (to be avoided)
So what I am after is some ideas where to look to sort this.
The machine in question is running Ubuntu 9.10 - other ubuntu machines that have successfully negotiated a connection were 9.04 versions. My machine can see the connection, and recognise the simple WEP security. I have even tried to connect with security disabled. When a connection is attempted, you get the animated spinning atomy bally things and after a certain timeout period, you are invited to re-enter the security password. It doesn't actually fail or report that it cannot connect. So it must be really close.
Settings on the phone are: ad-hoc, channel 1 wireless, channel 1 security, default IP is 192.168.3.x - I have even attempted 192.168.2.x (I'll try a .0.x or .1.x perhaps but at risk of conflicting with the home wireless set up) but in view of the fact that this will connect up to pretty well every thing else wifi, I wonder if there is some ubuntu driver I need to view with some suspicion.
Over to you Rob...