I can't suggest any software to do this out of the box but you might get suitable results manually in Photoshop or GIMP:
- Rotate/crop your image so that it has the same aspect ratio as the original video game.
- (Optional) Do some blurring/sharpening, depending on the image quality.
- Upscale your image to a multiple of the original videogame resolution.
- Run the Mosaic filter on the image using Cell Size the same as the multiple value.
- Downscale your image to 1/multiple, leaving it the same resolution as the original game.
- Using Save for Web & Devices, save it as a pallet-based format (PNG or GIF) with a small number of colours to match the original. At this stage you will also be able to tweak each pallet slot colour to adjust colours more closely to the original.
Afterthought: If your originals are all fairly consistent (size, angle, aspect ratio, etc.) you can probably automate most steps using a script calling on ImageMagick.