I've followed a bunch of methods, listing them below.
-Suggested methods from 4zK
-Jcgrey2's Method
-Ultric's Method

But I still keep getting negative sprites with whiteness where the magenta is located.
!Edit!: I am using Adobe Photoshop CS5
Help?

What program are you using?

Now I feel like an idiot.
Photoshop CS5

You should use GraphicsGale, MSPaint (Windows Vista and below), or Paint.net(?) to either sprite with, or take your sprite after you've worked on in Photoshop and use one of the other three programs to put it in palette.

Mmm. MS Paint always made me feel good about myself.
Do you know where I can download the Vista version? Have it.

!Edit!: Also, what should I save the file -exactly- as? I am saving it as 256 color -- .bmp but I'm afraid I'm doing the wrong type of bitmap. Is it 24 or 16...?

24, I believe.

It works now, but when in the menu it ends up being all scraggly sort of like this.

That's in the menu. Now when he's holding it, and looking to the right, it's normal. To the left, it looks scraggly again.

Copy palette.bmp from the Base.rte folder and paste it into your mod folder, and change the name to your sprite. Open up your original sprite in MSPaint, Ctrl A and Ctrl C, then close. Open the palette copy, Ctrl V, and re-size the image if needed. Save as-is, and see if the palette-copy sprite works.

Did I say I love you, because I do now.
I didn't realize this whole time you needed vista ms-paint.

There are probably other ways to get it to work, but that's the trick that I find easiest.

Thanks guys. Case Closed.

Were your images that were done in CS3 in 8-bit and in palette?

No they were done in CS5 on 8-bit with palette.

Sometimes resaving them in MSPaint, may fix that.