One thing you could do is download itunes.. It's free.. Set it to import to mp3 format, and select the bit rate you want, and let if organize the library for you. Then import your existing songs, and it will:
1. Reset the bit rate
2. Move them to a new directory so they dont' overwite the old ones.. (You never know if you want to try again...)
You can't go to a higher bit rate and expect it to sound any better. Whatever bit rate was used when the file was created is as high as you can go, but since it sounds like you want to go down, this ought to work for you. I wouldn't go below 128K; it prolly won't sound too good on the road if you do..
There are probably others, but since I happen to have itunes, that's what I use.