I saw a posting back from August 2007 from "Summer is Gone", where he/she asked about Workgroup Manager generating negative User IDs (UIDs). No one responded back then and the thread is now closed, so I thought I'd contribute my experience with it today.
I had this problem on a 10.4.11 server that serves only as an OD Master. I had archived the OD database, set to Standalone, rebooted, and then restored the archive as a potential fix for some little glitches that we'd been having after 4 years of running the server.
After the archive was restored, WGM was creating negative UIDs during "Add User". I'm not certain that was the trigger, but it's the likely one.
The fix was to simply trash ~/Library/Preferences/com.apple.workgroupmanager.plist and relaunch WGM. After that, WGM once again started generating positive UIDs.