AccessDenied when sending Encrypt request to Amazon KMS

I want to encrypt a string using Amazon KMS services. My credentials work, I can use the client to get a list of keys, but I get a 400 when I try to encrypt my string. This is my code (I bet I'm missing something simple):

public static string Encrypt(string str, string awsRegion, string theKey)
{
     var keyId = "arn:aws:kms:" + awsRegion + ":0987654321:key/" + thekey;

     using (var client = new AmazonKeyManagementServiceClient(AWSId, AWSSK, RegionEndpoint.USEast1))            
     {
          var req = new EncryptRequest
          {
               KeyId = keyId,
               Plaintext = new MemoryStream(Encoding.UTF8.GetBytes(str))
          };

          var blob = client.Encrypt(req).CiphertextBlob;
          return new StreamReader(blob).ReadToEnd();
     }
}

What could be the cause of this?

I also have my profile set up in visual studio.