Creating new ringtones for the 9500

Yes (MP3, WAV, MID, AMR, AWB, etc.). See the "Create ringing tone" app/feature in Nokia PC Suite (download latest version from http://www.nokia.com/pcsuite).

The only trouble is that the Nokia PC Suite will only convert from MIDI files (or has that changed in the new version?)

What can I use to change from MP3 to MIDI?

The 9500 will natively play mp3 or wavs as mentioned earlier, the music player in the media folder accepts them as standard. Just use the file manager in PC Suite to copy the mp3 's over to your phone or mmc, and then when choosing ring tones browse for them using the option on one of the screen buttons (page 82 of the manual).
Or you can install the free Oggplay program to play OGG encoded tunes which take upto 1/2 to 2/3 of the space as an mp3 depending on what bitrate you choose.

I know it can use mp3's as ringtones, but mp3's take up A LOT of room, I have a particular track that I want to convert to MIDI so I can create a proper ringtone, as the file I have is too big to also play on my kids series 60 phones while it is in mp3 mode.

So, what's a good program to convert mp3 to MIDI, so that I can then use PC Suite to create a ringtone?

Sorry I misunderstood as the original post did not mention MIDI.
I am unaware of any program that can convert mp3 to mid files. I know mid files take up very little space, but any tune I heard in midi didn't sound right to me.

What I used to do,and still do, is clip the track I wanted to a small section (how long does a ringtone need to be?) and then encode into OGG and put it on my 6600 and now my 9500, there are OGG players for both s60 and s80. i also used to have a few OGG ringtones on my 7650 and there wasn't much memory space on that.

(Edit) I have just done a quick google earch for a midi to mp3 converter and there are some listed here , try a trial version, or search some more for freeware.

You can't convert mp3 to midi really. Midi uses a device's built in instrument sets- think of a midi file as sheet music. In fact, that's pretty much what midi is. MP3 is a recorded audio file and sounds the same on every device. Midi is instructions that say "horn sound for four beats, snare drums go here... etc..." and sounds totally different depending on what instrument sets are on a device. All the midi music you hear and download has been written on a computer and played by nothing (some keyboards etc... will output to midi, but this is not the typical way midi music is written).

What I do is find an mp3 I like, chop out 20 or so seconds I like, and use it as a ringtone. The phone even without an mmc has 80 megs, and a little 20-30 second sound byte for a ringtone is like half a meg. I wouldn't worry about the size. You could keep it at a low bitrate (you can't tell the difference, it's not like the 9500 is an audio system) for even smaller files.