In the first bit of your post it sounds like somebody had already configured a "Restricted Groups Policy" for the "Remote Desktop Users" group, which explains why it "emptied out". That's not a stock OS feature-- somebody configured that at some point. You got around it by either modifying the GPO that was "emptying out" the group, or by making a new GPO that applied after the existing "Restricted Groups"-containing GPO to override the setting.
The next bit-- the "You do not have access to logon to this session" bit is a bit more confusing. I've been trying to repro it on a Windows Server 2003 SP2 32-bit Std. machine for a bit now, and I can't come up with a repro condition.
If you would, open the "Terminal Services Configuration" tool on the machine, highlight the "Connections" node in the left pane, and bring up the "Properties" of the "RDP-Tcp" object in the right pane. Have a look at the "Permissions" tab and see that "Remote Desktop Users" is granted "User Access" and "Guest Access" (the stock permission).
Failing that, I'm not sure w/o being able to repro it. What service pack level are you running of W2K3?
(BTW: I've got a similiar background to you-- I started on Unix and moved over to Windows grudgingly. Group Policy is incredibly useful once you get over the quirks. I script Windows machines like a mad man because I can't stand to do the same work more than once. The built-in Windows command shell is utterly inferior to any Unix shell, but it can be coaxed into performing most tasks...)
Oh-- they're Windows XP machines. I didn't realize that. That changes things. I thought these were servers you were trying to access w/ RDP.
My psychic powers say that you're seeing the "You do not have access to logon to this session" message because there is someone already logged-on to the PC and the user logging-on with RDP doesn't have "Administrator" rights on the Windows XP machine. Windows XP can only host one RDP / console session at a time, and if someone is already logged-on only an "Administrator" user can remotely "bump them off" with RDP. All other users attempting to logon w/ RDP will receive the message you described above.
How does that look?
To investigate the "Restricted Groups" policy more, run the RSoP tool on the WinXP clients and see if there are any GPOs enforcing a "Restricted Groups" setting on "Remote Desktop Users". In a network I setup, for example, there would be. It's a common way to grant groups access to RDP on clients.