Got it all worked out. Cingular was upgrading their BIS servers (I think migrating the service from RIM to their own?), and after upgrading that everything worked. It resent the service books automatically, so that probably resolved the issue.
Using the desktop redirector with Lotus Notes seems to be working correctly so far.
Thanks again for the help!