It turns out that there were actually one root ca and three other ca:s in the domain. I
only added the root ca and one of the other ca:s to the store. Once I added all the
certificates to the store everything started working as expected. Now I just need to
recreate everything on a new machine to make sure I didn't miss anything.