I stumbled upon this issue while configuring bacula on a 2.6.x based system on an IBM 4560SLX tape library.
The open() behaviour of st was changed at 2.5.3 to conform with SUS (blocking) and what the other Unices do (timeout). If the device is opened without O_NONBLOCK, the driver waits for some time (default 2 minutes) for the device to become ready. If it does not become ready, an error is returned.
Bacula 1.36.x does not open the device with O_NONBLOCK and thus isn't able to cope with this change. The solution is either to upgrade bacula to a 1.37.x version or to use a 2.4.x kernel.
I'll probably clean this up and ask to add it to the bacula FAQ list.