Thanks for posting the error.
Hrm - I'll admit it's not one I've seen before. Sounds like a missing dependency though. Would you mind removing and reinstalling the Pi Store, if you haven't already?
Also, are you on a fairly new Raspbian image (I'm not aware of any problems with older images, but I'd recommend being as up-to-date as possible)? Have you removed any packages which came on the image?
Sorry for all the questions - I'm just trying to work out what it's most likely to be.
Thanks again for your help,
The Pi Store: the home of games, apps, tutorials and other content for Raspberry Pi - store.raspberrypi.com
Want to hear about new Pi Store content? Follow @PiStoreReleases on Twitter.