Success!

Thanks to you both for your input. Giving the database role CONTROL permission on the cert, and REFERENCE permission on the key, worked perfectly. We are good to go.

But I'd like to throw out a high-level follow up question to everyone:

We encrypt data in a database so that if anyone should backup/copy/steal the table the data inside is unusable. But if that person has sufficient server rights to be able to run a backup, or to copy a table, wouldn't that mean they have a high enough permission set to decrypt the data using the cert and key?

I guess I cannot immediately think of a scenario where someone could get access to the entire table but not have enough permissions to decrypt the data. I suppose if a web user somehow knew the schema and submitted a SELECT * FROM tblTheTable they might get all the data, but we deny our web users any permissions they are not supposed to have.

Just wondering...