Are you using a FC switch, is the library zoned correctly for the server to access the library?
Alternatively, sometimes you need to within the library change some of the FC settings for it to accept the HBA, so that WIndows can detect it.
You're right Windows need to see it before BackupExec can use it. No matter what patches or drivers you install from BackupExec, you need Windows to see it first for it to work.