In case anyone is interested, I figured out the problem, I didn't grant CONTROL permission to the SQL Server User for the Certificate that I was using in my connection...
I also tried creating a Symmetric Key on the certificate and modified the Proc to open the key before the insert is called and then close it after, but still...