After trying again, I noticed that the message displayed after attempting to create a new backup database is "New backup database created on selected share.", while the message displayed in the "critical_errors.log" file is "10:59:25 22-04-11 warning Creating backup database failed."
I tried deleting the share & LV, created a seperate (new) LV and even tried putting the DB on a regular share. None have worked so far. I still get the error in critical_errors.log and no tapes can be labeled.
Per Gr-R's helpful advice, there seemed to be filesystem corruption
Here's what needed to be done:
Disable Local Backup (Configuration -> NAS Settings -> disable Local Backup)
Delete the logical volume that contained the backup (any data on this LV WILL BE LOST!)
Fix the filesystem:
(From the console) Go to Extended Tools (Ctrl-Alt-X), Select "Repair filesystem on LV" (#9), Hit yes to continue, then REBOOT!