It's exactly as it says. Image must be 256x192 24bit. This means 256 pixels in width, 192 pixels in height, and with 24-bit color.
You said "change the name"... If you just renamed a jpg or a gif, it's not going to work. You have to convert it to a bmp. The easiest way to do this is copy and paste the image into Paint, then save it as a bmp (note that in the Save window, the Save type at the bottom shoudl be set to 24-bit).
Also, to create a skin for the M3, you need more than just one picture.
Mainnds.bmp is just the background for the main menu. There's also an image for the music player background, file list background, ebook background, a folder icon, and each of the main menu buttons.