If there are problems found with screen (and it's a widely used admin tool that may be left running on remote servers, hence a high-value attack vector), it's going to be harder to find and fix the problem.

If there are features to be added, they'll be harder to add to screen than tmux. Which means that with time, tmux stands a higher chance of becoming more featureful.

Both argue in favor of tmux in the long run, though there's no immediate need to ditch screen. As you note, screen's very widely available, which is a feature. Then again, so was telnet 10 years ago.

Screen lets each part of a split screen select a different existing window. Tmux makes both parts of a split part of a single window, so you can either have two things going in one split, or have something else going on in another window, but if you suddenly decide you want two existing windows side by side, you can't do it.

OK, I looked back and it's fixed now: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=621804. 6 months is a long time to wait. (Not that I'm criticizing Debian. It would never be fixed if it wasn't for the distributions patching it.)