I see several issues with PowerCLI and vCD 9.1. Is there no support for vCD cmdlets in 9.1?
I contacted some VMware contacts and the best answer I got was that I should try PowerCLI 6.5 instead of 10.x
I did that and was able to make a new-org correctly without error. I then upgraded back to 10.1 and was still able to run new-org correctly. I'm not sure if something was left behind from 6.5, but at least I'm able to do some work with it now.
I ended up getting this to work by importing the certificates from vCD to my local workstation. I needed to import them specifically to the Trusted Root Certification Authorities. Once completed, I was able to run this an other cmdlets that were previously failing.