Yes, exactly. We actually got DS his balance bike (the cheap $30 Chicco one from Costco) a while back, for his 2nd birthday. He was mostly too young for it then (even though he's fairly tall he wasn't tall enough to really ride it even at the lowest setting. He didn't start riding it around the house until he was about 2.5-3. Even then, he did just as you describe..just shuffling his feet around, never lifting both feet..i think it takes some level of balance just to walk around on it and not fall over.
Well, it's funny you posted this thread today, as today was literally the first day DS dared to lift both feet while riding his bike! He did it inside the house first, then begged to go outside to ride it. So we went outside, but at first he was still pretty cautious and would not do it the whole 10 minute walk/ride to the park. But then as we were leaving to go home he got some confidence and tried it..and he lifted his feet HIGH, it was nuts! So the balance must have been building there somehow all this time!! Definitely do not lose hope at all.
Don't know if this will work but i've put a URL link here of DS riding his bike and lifting his feet today. DS will be 3.5 in July.
http://flic.kr/p/ev6Bco