Okay, I got this to work by exporting the certificate to a p7b and importing it to my Nexus. Once that was done, I was able to set up my Exchange account. Not sure why Nexus even required this in the first place as my cert is a public one and my other ActiveSync-capable devices detected it fine...