I've found that occassionally you need to run 'nsrck'. This helps.
In the nwadmin gui, also try to mark the tapes as 'recyclable' under Volumes, Change Mode; then under 'recycle', change to 'Auto'. This causes some manual work, but once the tapes are marked to recycle automatically, you should be ok for the next cycle.
The only other thing to look at would be the retention and browse policies as specified in the client information. If a saveset is marked for browse, even one on that tape, then it cannot be recycled automatically until the browse time is over.
Hope this helps.