Jason, in zone 8b 'Black and Blue' Salvia should return for you without any special care. You may want to give them a little more time. I've noticed that in areas where I've mulched well they are really slow to show in spring. If they are goners, then I would suspect bad drainage issues or rodent predation more than cold damage. We have pine voles here and they like to eat all sorts of tasty tubers. Salvia guaranitica will often grow near stream banks in its native haunts so it likes more moisture than some Salvias, but, still, excess water during a long, cold winter can be a fatal combination. Also, they don't always pop back up in the same exact spot that they were the previous year. They tend to spread, like an edible mint plant, and can return a foot or more away from the original plant, so look around for the sprouts pushing up.
An FYI, for anyone storing the tubers... The tubers are just storage organs and don't actually contain any "eyes" or nodes for stem growth. You have to be sure to retain the stolons that are connected to the tubers because that it is from where the growth will emanate. If you plant just a tuber with no stolons, it will just rot.
