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


Why not read some more of our Development Help posts?