Okay, it found 69 updates to my installed packages, but I'm still not seeing anything for new packages.

The apt-cache search returned something like 200 results, so the data describing available packages is there - it just doesn't know where to find any of them, maybe?