I'm not 100% certain about Travan media, but I believe the 40GB tapes you're using are in fact 20/40 tapes, eg 20GB native, 40GB compressed. This is mearly a guide, and does not mean that you can actually get 40GB onto the tape. It assumes that you will get a 2:1 compression ratio, however in the real world you're more likely to get something like 1.2:1, which might explain why you're running out of space.
Assuming I'm right about the type of tape, the only thing you can really do is either reduce the amount of data you are trying to backup, or change to a higher capacity tape.