I just have a couple of questions. I'm mostly familiar with NT4 but we have a few Win2k servers which I work with, this doesn't sound like an OS issue so the stuff below might be relevant.
First do you have a valid networker license, or do you keep uninstall/install an eval version? Second, when you installed 6.1.1 and the server was disabled, did you try to enable the server from the GUI, or from the command line? or do you mean that the server service would not start? Third, after the second install of 6.1.1 you could now see the server/service was started?
About the autochanger first of all can Win2k see your DLT8k drives? Do you get valid SCSI b/t/l settings when you type the inquire command from a dos prompt? Most likely if you haven't changed any settings since your uninstall 0f 6.02 then all is well from the OS side. When you reinstalled the server did you run jbconfig? Did jbconfig auto detect a standard SCSI jukebox? If not, from the networker GUI go to setup server and set search for new device to never, then set enable new device to no, then close the GUI.
Next stop the Networker remote exec service, then navigate to your nsr\tmp folder and blow away everything you see. You might have a lock file that was kept during uninstall. Now start the networker recover service, the networker remote exec should start automatically. Connect to ther server then go to setup server selct search for new device now and then click ok. Go to your autochanger resource and look for the library/drives.
If still no luck I would recommend disabling the new device search, then stopping the services again, blowing the lock files from nsr\tmp, renaming your nsr\res\nsrjb.res to nsrjb.old, starting the services and rerunning jbconfig from scratch. Be warned running jbconfig will reset any custom label templates to default so you will have to recreate them after you have reconfigured the jukebox.
Hope this helps - Larry