One of my unscrupulous users decided to format his Windows XP NFTS hard-disk before he left the company.
Are there any Linux based tools that would allow me to rebuild the partition?
When searching for information this area of recovery is often referred to as forensics. You are going to have a tough time if the person did any sort of non-quick format. For Linux you can try testdisk which is in Ubuntu's repositories. Be sure to mount the disk as read only. And you might have an easier time if you use dd to create an image. This Linux Journal article talks about disk forensics a bit (not sure if you subscription to view it or not).