Using Photoshop do everything in this post:
http://www.scubaboard.com/forums/1974309-post63.html - with thanks to Jonix...
Using the healing tool with a brush setting of 10, zoomed in to 200% - click on just about every small spot and "heal" them.
A couple of the larger particles near his head, his entire eye/face and a couple on the tail were easier to just clone out. Cloning seems to work best when there's a simple or no pattern. I also used the clone tool along the vein near the top of the fishes back since it didn't heal right.
To use either the healing brush or the clone tool, every time you move to a new area, do an Alt-click to select a similar area as your reference point.
Then to get rid of the bigger red spots, a combination of a bigger healing brush, (I think 25 but I didn't keep track) then touching up with a smaller healing brush, and finally some interpolation using the clone tool for those areas on the fins too red to "heal".
Bump up the contrast slightly and you're done.
I didn't do this last step, but you could also select the entire fish using the magic lasso and then apply contrast/saturation/color enhancement just to it to make it "pop" more.
Not bad for a videographer huh?...