I think O2Jam is easy. Even that song you posted is nothing compared to even just hard difficult in Guitar Hero for me.
Really? Because what's hard about O2Jam is that you have to hold notes with a finger while playing (tapping) other notes with that same hand, without letting go of the long note. (Which is very frequent, as you can see in the video)
Pump it Up, in the arcades, is far more difficult than either. It throws 4 and 5 arrows at you at the same time, and this is a game where you're using your feet to hit the buttons.
I totally agree with you about that, feet-rhythm games are definately more difficult than both GH and O2Jam.