I have a slightly similar issue with a tape drive connected to ESXi 4.1, though mine is SAS and with no media changer robot.
If I boot up the host and tape-using VM with no tape loaded in the drive, the Guest OS in the VM fails to detect the tape drive as present, even if a tape is inserted. To clear the condition I have had to reboot with a tape inserted. Due to short service windows I have not had the opportunity to test if the problem goes away after a few hours of running in the tape-missing state, as by then the service window would have ended and there might be no recovery until the next service window.
But it would be interesting to hear if your problem goes away if you load a tape (any tape, though probably not a cleaning tape) into each drive before booting the host.
Also my affected Guest VM happens to use a recent Linux kernel to access the tape drive, is it the same for you?