Almost every high street photo processing shop offers a restoration service. Snappy Snaps certainly does
http://www.snappysnap...uk/photo-restoration/
but you'll probably find similar services available at Klik, Boots, etc. (It might also be worth checking out supermarket photo processing counters. I know that some of them used to offer this service but I'm not sure whether they still do).
Alternatively, a friend who's got one of the full versions of Photoshop (or GIMP) on his/her computer (and who actually knows how to use it!) should be able to do the job for you. After all, it will be Photoshop that's used by the professional labs anyway.
Chris