Hi, I had the same problem so I emailed Playbook support. The solution makes perfect sense if you're used to using App World on your Storm.
Here's what you do:
Open App World like normal
bring up the keyboard (swipe from bottom left)
hit the keys "r s t" (without quotes)
A message will popup saying that the service cache is cleared
Close App World and re-open it.
It's the same way one would reset App World on a Blackberry Smartphone. The service rep's instructions said I should restart the Playbook itself, but I found that simply closing App World after clearing the cache and opening it again worked great.
Hope this helps