I spent a couple of hours trying to figure out what was causing it, and after about two Vista re-installations later, I finally figured out what the problem was: The ATI display driver from Dell's website. The version they have is from May 2007. On a clean installation of Vista SP1, roaming profiles would work fine until I installed that driver. So I downloaded the latest driver from AMD's website, and luckily the problem was fixed in it.
This problem shows two things. First, it shows just how easy it is to blame Windows for problems that are not its fault. And second, it shows how some drivers are getting too intertwined with Windows. A display driver should not affect roaming profiles.
This is the driver that was causing my problem:
http://support.dell.com/support/downloads/...p;fileid=206423