They do not do the same job.
Titanium Backup can back up your apps/data on a schedule, as well as compress and restore multiple instances of data and applications. Titanium does a ton of other stuff as well, such as freeze or remove bloatware and fix access permissions. It will probably work for most backup and recovery scenarios you could envision with one exception: if your ROM won't boot (which can happen if you remove a vital system component using Titanium). If your ROM is dead, you can't run Titanium and can't restore whatever you deleted that's killed your ROM.
Nandroid backups generally back up the entire running state of the phone. If you make a Nandroid backup now and brick the phone by using Titanium to kill something you shouldn't have, restoring said Nandroid from recovery mode (before the phone boots) will get you back to running.
Titanium Backup is significantly faster than Nandroids after the first backup has completed, as generally it only will touch recently modified apps and data, and you don't change every piece of data on your phone on a daily basis. It can also be scheduled to run while you're asleep, ensuring that you have nightly backups of all your text messages, Angry Birds progress, etc. Backups can be compressed in the app automatically to save SD card space.
On the other hand, Nandroids have not been something you can schedule. They are something you have to sit down and initiate manually. When they're done, on most recoveries you have to select to reboot your phone, and historically they have not compressed the data (the newer recoveries do). A Nandroid is something you have to do.
Personally, I use both. I have Titanium Backup scheduled to back up all my apps and data on a nightly basis. This way if I lose the ROM or just flash a new one, I don't lose my progress in all my games and I don't have to re-configure all my social apps. I generally make a Nandroid before I do a major change to the phone, such as upgrading or switching ROMs, as those are the times when taking that 6-10 minutes is worth it.
Restoring a Nandroid generally puts the phone in the exact state it was in when you made the Nandroid. There are exceptions to this generality; however, I'm really not going to go into issues with kernel restoration on HBOOT 1.50 unlocked EVO 3Ds or quirks with ClockworkMod or other recoveries.
It used to be a Nandroid backup was an all-or-nothing event, then programs such as Nandroid Browser came to market that now allow you to pull individual data and apps out. These don't mean that Titanium Backup has been or is being replaced; it's just that one of the many, many features has been somewhat duplicated. You still have to take the time to make a Nandroid, during which your phone is off and unsuable. With Titanium it is up and running and you can make and receive calls.
Also, if Titanium were to make and keep three historical backups of a 14MB app/data, you could figure the storage use would be no more than 42MB. Were you to make three Nandroid backups, however, you're looking at maybe 500MB a pop for a full image, or about 1.5GB total. Then again, Titanium doesn't make backups of system components such as the kernel, wpa_supplicant, drivers, etc.
Both are great pieces of software, and if I had to choose just one, it would be Nandroid because quite honestly I would not have a working phone if I hadn't made some of those backups before installing ROMs of questionable stability. However, Titanium has ensured that under very, very few circumstances will I lose my old apps and data, even if I didn't install or restore them to whatever ROM I just installed.
I have some software from my HTC EVO 4G that made the leap to my EVO 3D via Titanium that occasionally I will bust out, and that's something you haven't been able to claim with Nandroids (although I suppose Nandroid Browser and such changes that).
Learn how to make and restore Nandroid backups, though. This could really save your rear end some day. Titanium is cool and useful as all get-out when you get right down to it, but it's not going to save you if your phone won't boot, and that's the only legitimate fear root users need to worry about.