Interesting!  Your hypothesis is close, but:

open("/dev/nst0l", O_RDWR|O_LARGEFILE)  = -1 ENOMEDIUM (No medium found)
write(1, "MESSAGE Can\'t open tape device /"..., 64) = 64
write(1, "DEVICE_ERROR\n", 13)          = 13

the open call itself is returning ENOMEDIUM, rather than the
subsequent ioctl.  This is explained in this comment
(device-src/tape-device.c)

 558    On Linux, with O_NONBLOCK, the kernel just checks the state once,
 559    whereas it checks it every second for ST_BLOCK_SECONDS if O_NONBLOCK is
 560    not given.  Amanda already have the code to poll, we want open to check
 561    the state only once.

This O_NONBLOCK should be set if the compile constant
DEFAULT_TAPE_NON_BLOCKING_OPEN is true.  config/amanda/tape.m4 sets
that constant as follows:

188     case "$host" in
189         *linux*) AC_DEFINE(DEFAULT_TAPE_NON_BLOCKING_OPEN,1,
190                         [Define if open of tape device require
O_NONBLOCK]);;
191     esac

so I wonder if your $host doesn't include "linux"?  I assume you've
downloaded the Amanda source -- if you run config/config.guess, what
does it return?  For me:

dustin@euclid ~/code/amanda/t/amanda [z8946*] $ sh config/config.guess
x86_64-unknown-linux-gnu

We're making good progress on this, and getting into the seamy
underbelly of tape devices on Linux :)

Dustin

-- 
Open Source Storage Engineer
http://www.zmanda.com