Wrong Way Round
You may find that you've got it the wrong way round - the USB standard allows a device to request up to 500mA, but not all hosts can cope with that, especially if they're supporting multiple devices. A four-port hub with a total power capacity of 1.5A is technically within spec, but can't support four 500mA devices, whereas it can support two of those and two 250mA devices.
Laptop USB ports tend to be built down to a price/power budget and may struggle to give 500mA. It's also the case that many desktop PCs were capable of providing much more than 500mA, so they would be less likely to be fussy about things.
What you do find is that custom USB power chips exist that allow the device to draw a given maximum power from the host, and that if the current drain of the backlight and processor is high enough, all the USB current goes to supply that and none is available for battery charging. Similarly, if the device has asked for 500mA and has been turned down, it may opt to only draw the 100mA it's allowed without asking and power the electronics but not attempt to charge the battery.
The final point is that Apple may not claim that the device conforms to the USB spec. I believe that they make no such claim for the iPod. Electrically and from a software protocol perspective it may be perfectly compliant, but the spec also requires use of standard USB connectors and the iPod has a custom one. I don't think there's a USB logo on a standard iPod lead for this reason - it's not compliant with the mechanical aspect of the standard.