I ran across this bug on GitHub on a <paginator>, turns out you need to reference the $parent scope. Thinking about it, it's probably because <paginator> has an isolated scope. So the original value was being copied, but never updated inside the isolated scope.
Old and Busted:
<paginator data-ng-show="isPaginated()" ...>
New Hotness:
<paginator data-ng-show="$parent.isPaginated()" ...>