I've tried uninstalling and reinstalling several times, to no avail, but have finally cracked it. Here's what happened:
I originally did the jail break / unlock on a Windows 7 64bit RC machine, with 64 bit iTunes - not sure if it's "supported", but it seemed to work aside from one error when the firmware was being restored to the iphone - it read something like "received an unrecognised response from the iPhone".
I was bricking it as I thought i'd bricked my wife's 3G, luckily, it seemed to come back after i powered it off. When it came to life, cydia/icy were installed so I assumed all went well, I unlocked and restored all her stuff and I thought all was well.
What I didn't notice is that on power on, the apple logo always showed, instead of the pineapple logo - yet the device was still jailbroken and unlocked, so I thought nothing of it. Restoring the download apps then displayed the problem I originally reported.
Today, I wiped everything, JB/unlocked, pineapple logo showed, I restored apps from backup, etc - still had the problem.
After one last JB/unlock, I skipped the restore and downloaded the apps and they worked fine, so whatever messed up in the original JB must be stored in the backup file.
Right now, all is working, and she is a happy bunny!
Thanks to all for the advice!