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.
Edit:
On newer versions of Android the path should be
Menu > Settings > Security > Device Administrators