What I've noticed is that if you owned/had the theme (or tweak) installed on your iPad under 4.x, after you upgraded and re-jailbreak on 5.x, your iPad is still able to download the tweak.
However, if you never had the tweak before, you can't get it. So, one may be running it fine on his/her iPad, but another can't install it. That's why people get that "can't verify" notice.
The only thing I can suggest is to contact the developer. I am sure they have to tell Cydia, somehow, that the tweak is fine to run on iOS 5.
Hope that makes sense and clarifies things a bit.
Marilyn