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?
If someone steals the backup file or mdf file, without Database Master Key he can't decrypt the data. You also should remember that if you want to restore the db on another instance you must restore DMK. And the DMK should be backuped and protected with a password and proper access to that file. If someone has select to a table where are encrypted columns, still he need permission to key to decrypt the data. You should thinking of both an encryption and permissions.
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.
I don't know how big will be that web application but remember that encryption on sql level isn't easy scalable, with www maybe you should start thinking about encryption on another application tier.