I have used the Mac version of this program with a fair amount of success:
Data Rescue 3
As others have said, with only a reformat and no data written, your chances of recovery are good.
Be aware though, that recovering data will take a long time. Also you end up with files (and file fragments) only- Nothing is sorted into directories, etc.
BEST OF LUCK, SIR!