If you must upsize a low-resolution bitmap, investigate some advanced scaling programs like Genuine Fractals.
Or if you only have Photoshop, scale up in many, small steps. Go to something 2 - 4 times larger than your target size, apply some dust and scatches filter or Blur to smooth out the blotchyness, then scale back down to the target size.
If it is graphic, rather than photographic, you may be able to manually paint out, or lassoo and blur out some of the artifacts when it is at the large size.
Apply sharpening only AFTER you have arrived at your target size, never before, because you will only magnify the artifacts.