Hey Mr. Toe,
I suspect you might work at the same co. as me, cause that just happened to me recently as well.
My Notes just got automagically reconfigured through some kind of remote configuration to use the 'local' database instead of server copy directly. In addition, when I try to pop open my Notes Inbox, it asks me for the location giving me "local" as the default. I have to hit OK to get it to look local, which I suspect is the problem.
My Sync Station Settings had to be changed for each of the syncs to point to the local database directly. If you pop open the sync station settings, hit settings for the contacts, you'll see the the "Use default" is probably selected. In my case, I don't think Notes had a proper default and that's why it couldn't find the PIM.
Unselect the checkbox, put "local" in the select server box, and put the name of the file in the next box. Get the name of the file by opening your inbox in the Notes client, and look at the "database properties". You'll see something like "mail\mrtoe.nsf". Finally, stick in your Notes password. If you're not using "local", you'll have to get the appropriate settings for your setup.
You'll have to update all of your Notes syncs with those settings, and then you should be good to go....