After talking with josephmurray in IRC, he told me to (a) look for "stuck processes" and (b) to try and manually "Execute Now" the job from the CiviCRM cron page.
The latter didn't do anything more than my cron job which was set to run every 5 minutes.
As it turns out, the stuck process was the cron job itself. A "ps ax | grep php" showed the CiviCRM cron job running.
I wanted to know how long it was running so I ran 'ps -p 29753 -o etime=' (where 29753 was the pid of the process from the ps ax command above). It showed that that one cron job had been running for a number of hours. I deduced it was clearly "stuck."
So, the thing to note is that even if your cron job is set to run frequently, the log will show it running and finishing... but if your CiviCRM Mailer settings only allow 1 cron job to run (as mine do), then you're basically only seeing the cron job start, detect that another is already running, then shut down.
For me, the solution was to "kill 29753" - then the next time cron ran normally, it marked the mailing job Completed.