Ok, a few quick questions ....
1) Do the paths get added in AutoCAD, meaning can you click the support file options in the preferences window and see the paths properly set?
2) Have you verified if the paths are being properly written to the registry for the profile you are selecting?
3) Are any of the paths being duplicated in the support path options?
The reason I ask is because I have found instances where you may be able to add another instance of an existing path to the current path, i.e. there may be 2 instances of "C:\\Program Files\\AutoCAD 2007\\Support;" This will cause an issue on some installations of Windows XP, I think due to the registry handling functions either within XP or AutoCAD itself. This is not limited to R2007, but can rear its ugly head from R2000 through R2007, particularly on unpatched versions of A2k, A2ki, and A2k4 running XP w/sp2.
I have not found a resolution to this as of yet, but I am always looking for something to help in its resolution.