Did you try removing the plastic insert in the car mount that's there specifically to take up the space that would otherwise be filled by a case on the phone?
..There is a seidio case (surface) that looks almost like a twin of the rocket fish case and I'm thinking of trying that I think might fit as well.