Either way, you might have trouble starting to charge if the laptop is in powersavings mode (hibernating) but from what you write here, that does not seem to be the case.

I have exactely the same problem. Sometimes it works, sometimes it refuses to charge after a few seconds. I couldn't find the cause (I tried several pc and several cables), I'm sure there's a hardware bug in the N900 but it's very hard to find.

This is a common problem for me.
In my experience many devices (with USB charging) can't get enough power even from desktop computer's USB port.
The amount of attached USB devices in the USB-hub can affect to this. For example, charging might start working after you remove some other USB device from the computer and try again. Every device consumes power and the output of USB port is very limited
(According to USB 2.0 specs: 500mA at 5V for one port which is usually shared with many devices).

i hand the same problem with my desktop, re-instaled pc suite and the cable drivers and it fixed it.

I had the same message come up on my desktop too, unplug and replug worked for me fine. I figure it was just a bad time to access the rail on the board.

I've noticed this message before, but only when trying to charge the N900 from a power source that supplies less than 1.5 Amps and even then, ONLY when the battery is low. not dead. Low.

A typical computer USB port is good for 500ma, which is less than half the power the N900 charging driver is looking for.

I find this happens occasionally when the laptop itself is drawing charge. I get the feeling it can't quite power the USB ports enough at the same time as feeding its own battery.

I wait ten minutes for the lappie battery, and then try again.

I just want to emphasize what jarnori said. Some ports are shared. So try to disconnect all the other devices from all other usb-ports first.

I am getting the same error message for a few days now (it worked before for over a month on the same laptop) and I believe it is related with the Nokia Phone Updater software which updated to the last release and replaced some of the drivers the day this started to happen.

This is what I observe:
1) I plug the USB cable to the very same port I had earlier and the phone will start charging.
2) The phone will charge over USB until I select one of the connection methods (either Mass Storage or PC Suite), 1-2 seconds after I select the method
and option I get the error: "not charging. insufficient power"
3) I am using the original Nokia USB cable as I did before
4) My laptop uses a docking station and this happens disregarding of using the power and the laptop battery charging or being full
5) I checked the USB port and confirmed it has 500mA, I also disabled power savings on the port, and rebooted both computer and N900 but did not make a difference
6) Under Device Manager > Show Hidden Devices > Wireless Communication Devices > I see "Nokia N900 USB Phone Parent" showing a question mark indicating an error with the driver. I tried rolling back the driver, uninstalling all Nokia drivers, nokia software, rebooting, etc. But I still get the same error (important to select the option to Show hidden devices from Menu > View)

I also get this message sometimes but I leave the USB connected after 20 seconds or something is usually will start charging