Probably jsut need to do a
sudo apt-get update
first, and if testdisk's still not available you may need to use the universe, restricted, multiverse "sections" of the repos, see the possible dup. question "Unable to locate package" while trying to install packages with APT or Ubuntu's Repositories help.
But are you positive your partitions were all deleted? Maybe the bootloader was just changed... If you're still running Ubuntu, or running a live dvd/usb, the command
sudo parted -l
sudo fdisk -l if you're using MBR only) should list all your local disk partitions & current device names, maybe they're still there.
If they were all deleted, then further writing to the disk could overwrite more data, and doing as Takkat suggests would be the best idea. I don't think you can repair a hard disk with
testdisk while it's mounted anyway, and having a backup copy to "play/fix" with would be the safest option.