Ok, I have not tried reinstalling Firefox, but I do have a breakthrough. 4shared.com also has a "remember me" checkbox at the login prompt, and it never remembers me! Now I don't visit that site nearly as often as I do this one, but "remember me" should remember me, and it doesn't.
When I set this machine up, I did a clean install of vanilla XP, and a clean install of Firefox v.3. I never even ran internet explorer, as I had download the Firefox install file previously.
So, what gives? I deleted my cookies & the cookies.sqllite file, but the remember me thing still doesn't work. Anyone know if something in about:config could be the culprit?