mate - you really need to get it onto a scanner to do any worthwhile photoshop work on it - a digital camera shot just wont cut it. My scanner does a 1200dpi scan, and its only a cheapie Canon. If you have a friend who can scan the photo for ya, zip it up and I'll see what I can do for you. Just remember to scan at the highest res you can, cause the more data you have to start with, the more you can play.
BTW - I don't know what kind of photo places you have in NZ, but I know Fletchers Fotographic in Sydney does digital restores for about $60 for normal sized image.