UPDATE.
I believe I have isolated the problem, and this is what happend. Please bear with me with the series of unfortunate events:
1. Before the new network was set up, every computer had a local account, most of them Admins. For instance, a PC had an account named "John Smith" wich was mapped to a folder named "John Smith" in the Documents and Settings directory.
2. After the installation of the server and the domain-based network, I run the Connect Computer Wizard that comes with Windows Small Business Server 2003, as suggested in the User's Guide.
What this wizard did was "convert" the local accounts into domain accounts, so the new user used the settings from the previous local user, i.e.:
Before: User "John Smith" loads the "John Smith" directory
After: User "jsmith" loads the same "John Smith" directory
This was an advantage because it made the move pretty straightforward. However, the big problem started when I had to re-install and re-configure the server, so:
3. After installing the server and creating the domain, users and computers (using the same ones that were previously configured), client computers logged in just fine, but something was off: Noone -including me- could access other client PCs on the network.
As some people suggested, I had to re-join the computers to the domian, even though the user names and computer names had not changed.
Anyways, I went to My Computer, Network Settings and used the Windows Wizard to configure the network settings, as I figured would be quick and pretty easy.
I was wrong.
The wizard completed the operation just fine, but after rebooting and log in, I noticed that the user settings had been lost.
After a few hours of heavy head-scratching I realized what had gone wrong: Windows had created a new, empty profile using the domain user name as the directory, so now when "jsmith" logs in, Windows no longer loads the "John Smith" directory with all the settings, instead it load the new, empty "jsmith" directory.
Everything is still there in the "John Smith" folder, now I only have to figure out how to move it to the new "jsmith" folder.
I can't simply just copy it, as Windows refuses to do so stating that it cannot copy some crap files like "index.dat" or some other crap.
So I was wondering if deleting "jsmith" and renaming "John Smith" to "jsmith" would do the trick.
Oh, FYE, the two PCs I wrecked are running Windows 2000 SP4.
Well, at least I learned something from this experience. Always, always backup your user profile.