I can't speak for American Eng, but I've never been aware of a difference.
You're on the right track with the countable/uncountable idea. But there's also a difference between abstract and concrete. With 'choice' you tend to get comparative adverbs like 'wider'. Choice in this sense is talking about a range of possibilities that someone can choose from.
Choices have been made already. You can 'regret your choices'.
PS To answer your original question, we need more context. But if you're taking about a range of things available to choose from, 'More choice' is right. Rarely though, when the choices have already been made, 'more choices' would be possible: 'In his life, he had made more choices that were right than ones that were wrong.'.