has the modem ever worked over 37kbps?
have you been using it on the same phone line?
modems are a lot more prone to line condition than broadband connections, if you havn't already, try it in another room in your house, and that might do the trick.
also, go to device manager> modems> properties and check to make sure the "maximum port speed" is set to its highest value.
good luck,
-Vivan