I had that happen last night. My gym put in new spin bikes, same deal with SPD cleat one side, platform w/ toe clip on the other.
I wore the same bike sandals I use on my road bike.
I got the Right foot out OK, but on the Left side I was almost ready to take my foot out of the shoe to escape. I had to twist my foot so hard to clip out that it hurt my ankle.
Bikes are Keiser M3 Indoor cycles. http://mseries.keiser.com/m3.html .