How can git pull be up-to-date and git push fail?

I'm trying to explain this behavior to a co-worker, and how to solve
it:

% git pull
Already up-to-date.

% git push
error: remote 'refs/remotes/origin/flexify' is not a strict subset of
localref 'refs/remotes/origin/flexify'. maybe you are not up-to-date
and need to pull first?

I believe he is using git 1.5.0 and that the above was tried from the
master branch.

So, I'm confused: I would have thought the way you solve the problem
in step 2 is by executing step 1.  Would he need to do this:

% git checkout flexify
% git pull flexify:flexify
% git checkout master
% git push


Bill