You got the global setting right.
The job properties should also be Append to media, overwrite if no appendable media is available.
Still not working? It sounds like you might be manually dragging tapes into the media sets? This could be causing you some problems. If you can, perform a quick erase on all tapes in the library for the affected media set prior to the next backup.
If you're trying to gain better control over what tapes get used for certain jobs then consider partitioning the library into several sections, and define jobs to just those partitioned sections.