First, I think, you should simply try to upsample the image in Photoshop so that it has the required effective resolution and go from there.
And if necessary investigate dedicated upsampling software.
You could always use a blur filter or the blur tool.
C.Pfaffenbichler mentioned upsampling but didn't say how: Image - Image Size, then select Bicubic or Bicubic Smoother as the upsampling method.
However, if the image has already been upsized using something like the Nearest Neighbor resampling algorithm, to where each square block of solid color in the image is really a block of multiple actual pixels, all the same color, then Brett's suggestion may be a good approach.
Or you could downsample it so that each block of color really DOES occupy just one pixel, then use either the aforementioned upsampling or one of the fancier upsampling tools. An example using OnOne Software's Perfect Resize 7.5 (which has a free trial period).