I'll have to have a look and see if they've actually filtered into the UK store this time, we didn't get the categories in the last refresh of the AppStore. Or at least, it didn't show up on mine.
I don't think we have got categories yet although they might be there now. There definitely is room for improvement in the Apple TV's UI. Maybe when a lot more apps are added Apple will have more of an incentive to update it and offer a much more friendly way of finding and organising apps.
I'm in Canada too, but using a US iTunes account, so I'm not sure if this is a geo problem or something else.Did that already