When installing Lotus Notes Traveler on a single domino server, you would normally not install the Clustering Support feature on the Domino server.
The result is that you will see a lot of “unable to find replicas for ‘database name’ on ‘server name’ ” errors ( and other Lotus Notes Traveler related errors ) in the server log.
According to an IBM Technote ( # 1303737 ) this is normal behaviour. To solve the problem, add the Clustering Support feature to your Domino installation.
UPDATE 28-May-2008: This issue has been addressed in APAR LO29715 which can be found on the Lotus Notes support site here.
However if a customer wishes to resolve before the maintenance release is available they can copy cldbdir4.ntf from the data directory of a Domino Enterprise Server to the data directory of the Domino Messaging server and restart Lotus Notes Traveler.