My parents had a sort of similar experience, in that they gradually grew disillusioned with the synagogue they used to go to (my dad and I beating the rabbi in a theological argument had a lot to do with this), but rather than being turned away from worship as a whole (which is what happened to me), they found another synagogue with a rabbi whose attitude was more in tune with theirs. Both places and both rabbis were from the same denomination (United Synagogue), but the one was just much more welcoming to people who didn’t necessarily do everything by the letter than the other.