I had a very similar experience teaching my wife. The thing I've found fascinating is that counting in binary only initially seems hard to people because, in most cases, people really don't know how counting to 10 (10 decimal that is) actually works. I actually remember having a similar feeling when I first took discrete math, I suddenly realized how little I understood of things that I had previously considered basic.