The amount of space between the categories does give that impression a little. Nothing a change to the grid won't easily fix.
Hah, interesting. It's definitely a balance between showing the categories, or some of the categories so that users know they're there to navigate. Each category will be getting grayscale icons - we'll see if that helps at all.
If you need more text, grab the highest rated app in that category and display it below the name.
I think icons would fix the problem nicely, kind of like the App Store layout uses them.