If you ever need to uninstall Lotus Notes Traveler from your Android device you need to first of all remove Traveler from your device administrators list. If you don't do this the uninstall will fail.
To do this go to...
Menu > Settings > Location & Security > Select device Administrators.
Then you should be able to complete the uninstall normally.
On newer versions of Android the path should be
Menu > Settings > Security > Device Administrators