I don't suppose the Staples labels came with a LabelCreator Pro CD? The online Staples store sells them that way. You can download a free 30 day trial from labelcreatorpro.com.
I used to use Mediaface When I bought labels that weren't compatible, LOL, I'd peel them off and stick them in an old Fellowes label sheet that I had used earlier, with the labels already peeled off. It wasn't a great solution.
Later I got an Epson printer (and Epson software) that could print to CD's (either the printable ones, or CD's with labels attached),