Oh yes! It works now!

The reason - you may not believe this - was the USB cable! I replaced the Huawei USB lead with one from my USB hub and it works great now.

Very weird indeed. I even got the log writings when connecting to the router, the flashing blue light on Huawei and everything. And the log writing about the "address not accepted" is not appearing anymore.

(I also had problems with the same cable when connecting to PC, and the new one works great there too.)