Why does git status show branch is up-to-date when changes exist upstream?
What the status is telling you is that you're behind the ref called origin/master which is a local ref in your local repo. In this case that ref happens to track a branch in some remote, called origin, but the status is not telling you anything about the branch on the remote. It's telling you about the ref, which is just a commit ID stored on your local filesystem (in this case, it's typically in a file called .git/refs/remotes/origin/master in your local repo).
git pull does two operations; first it does a git fetch to get up to date with the commits in the remote repo (which updates the origin/master ref in your local repo), then it does a git merge to merge those commits into the current branch.
Until you do the fetch step (either on its own or via git pull) your local repo has no way to know that there are additional commits upstream, and git status only looks at your local origin/master ref.
When git status says up-to-date, it means "up-to-date with the branch that the current branch tracks", which in this case means "up-to-date with the local ref called origin/master". That only equates to "up-to-date with the upstream status that was retrieved last time we did a fetch" which is not the same as "up-to-date with the latest live status of the upstream".
Why does it work this way? Well the fetch step is a potentially slow and expensive network operation. The design of Git (and other distributed version control systems) is to avoid network operations when unnecessary, and is a completely different model to the typical client-server system many people are used to (although as pointed out in the comments below, Git's concept of a "remote tracking branch" that causes confusion here is not shared by all DVCSs). It's entirely possible to use Git offline, with no connection to a centralized server, and the output of git status reflects this.
Creating and switching branches (and checking their status) in Git is supposed to be lightweight, not something that performs a slow network operation to a centralized system. The assumption when designing Git, and the git status output, was that users understand this (too many Git features only make sense if you already know how Git works). With the adoption of Git by lots and lots of users who are not familiar with DVCS this assumption is not always valid.
This is because your local repo hasn't checked in with the upstream remotes. To have this work as you're expecting it to, use git fetch then run a git status again.