Since the OS has been re-installed the disk will have been formatted so I'm not optimistic about you getting anything back. The first thing you need to do is stop using the disk. The more you use the disk the less the chances of recovering anything.

If you want to try recovering data you should do that either by booting the laptop from a LiveCD such as Ubuntu-Rescue-Remix and have another disk attached via USB to save any recovered files to, or install the recovery tools on a different computer, take the disk out of the laptop and attach it to that computer.

I've previously used PhotoRec to recover some files from a disk (ext3 I think) that had developed some sort of fault that had screwed up the filesystem, but in that case the data was still on the drive, it hadn't been overwritten and the disk hadn't been formatted.

A professional data recovery service may be more successful, but they usually cost a non-trivial amount and there's no guarantee they'll get anything.