Using the long file name in quotes is the correct procedure. I'm not sure why that doesn't work, because I have a bunch of batch files where it works fine. Of course, if you're actually executing the command:
cd "all users"
... you do realize you have to be logged into the Documents and Settings folder, right? How about trying:
cd "\Documents and Settings\All Users\"
... and see how it works. That works on my 2K system.