OK, so I decided to boot up BT to see how those guys have theirs setup. BT uses KDE, so I booted my Kubuntu VM back up.
I noticed that everything was 'command;sudo -s'. Sure enough, tried this on Kubuntu and it worked with no problem.
When I go back to Ubuntu and try the same, I receive "there was an error creating a child process for this terminal." Kind of weird since the command works fine from inside a terminal.
I tried switching it around.. "sudo nmap", but it just goes back to closing right away.
So it looks like KDE will work

Getting closer at least, hopefully I'll figure out something with Gnome.