from what I understand (could very well be wrong) unless a device specifically requests more power, a usb port will only provide 100 ma. once the device requests more, the port will give 500 ma.
my phone also will not charge when plugged into my computers USB port. and it uses a 5v 500 ma wall charger with a USB connector on the end.
all other devices that need the full 500 ma work and can draw the full 500 ma (GPS, EVDO modem, external USB drive, and they show as drawing 500 ma under device manager) plugged into the same port so I know the computers port and USB drivers are OK.
my guess is the phone wont charge with 100 ma and its not requesting the full 500 ma for some reason (not fully USB complient?). linux may treat the ports different and just set them at full power all the time.
I myself have never heard of the 100ma/500ma variation in USB current allotment, although I doubt this is the reason your phone can't be charged through your computer's usb connection.
Even though your wall charger can provide up to 500mA, it certainly doesn't draw that much current during use. Theoretically if you just wired the pos and neg wires from two usb ports together you would get 5v @ 1A.