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.
I think icons would fix the problem nicely, kind of like the App Store layout uses them.
If you need more text, grab the highest rated app in that category and display it below the name.