I don't think your problem is related to Managed Preferences, but you might want to double-check to ensure that you are not restricting access to the computers (Computers or Computer Groups section of Accounts in Workgroup Manager).
This sounds like a general inability to log in to any user account that resides in Open Directory, although at one time you must have been able to. This is what I think happened:
When things were working, Steve and Sally logged into their own Macs and chose to create a Mobile Account. (Sounds like they're also using Portable Homes, too.) When the Mobile Account is created, a copy of the user account is placed in the client's local LDAP (10.5) or NetInfo (10.4, 10.3) domain. The user's password hash is also copied to the local machine - from the Password Server database on the server to the Shadow Hash database on the client. The client's copy of the user account contains a reference to the original in the server's directory domain so that the two can be kept up-to-date.
However, the way it works is a little different from what most people may think: Whenever Steve or Sally logs into his/her own Mac after creating the mobile account, the client-side copy of the account will always be used (even if the server is available), because it is in the local directory node, which always has first priority in the authentication search path (search policy).
At some point, a change was made to your server, causing users in its LDAP (Open Directory) domain to lose the ability to log in. This would explain why Sally cannot log into Steve's Mac, and why Steve can. (Remember that Steve already has the mobile account there, but Sally doesn't.)
Now this change wouldn't necessarily affect the home synchronization feature via Portable Homes. That, along with other managed preferences, could still be working, largely because the clients keep a cache of that information, and because that information can be accessed in the directory by simply reading account attributes (no user authentication).
So at this point, I'd say that the problem resides either in your server's LDAP domain or in its Kerberos configuration.
Let's start with the LDAP domain: Have you changed your server's local (behind-NAT/private) IP address lately? Or did you start up NAT after Open Directory? If so, you may have to update the address and hostname in the server's LDAP domain via *slapconfig -changeip*:
sudo slapconfig -changeip (old IP) (new IP) (old name) (new name)
In short, the IP address should be the local one and the hostname should be +the DNS entry that resolves to that local address+. There are a couple of ways to accomplish this, such as hosting a private (behind-NAT) DNS zone. I've answered a similar question here:
http://discussions.apple.com/message.jspa?messageID=5933263
The hostname is important not only for the LDAP process, but for Kerberos as well. The Kerberos realm name will be the server's hostname in uppercase. I've also answered a question relating to manual Kerberization and the things to check:
http://discussions.apple.com/thread.jspa?threadID=1251391&tstart=0
Hope this helps!
--Gerrit