Can traces of previous operating systems be detected after new install?

The command you are looking for is called shred on Ubuntu I believe. Google it, I am pretty sure it comes preinstalled on the Ubuntu DVD.

If you just reformat a drive, the previous contents will still exist on the drive, and it is fairly easy to get them. This is because normally there is no reason to waste the time to clean up the data. There are marked as unused and left until they are needed, but the data is still there.

There are programs, like shred, that methodically erase all data from a hard drive by overwriting it with a zero.

This is probably good enough unless you are worried about the NSA.

You might also want to think about encrypting your hard drive. This does slow down the system any time it reads or write to the hard drive, but current encryption is pretty strong.