Well doh, my phone hardly ever has a connection.
Funny thing, the problem persists even after it was connected to the Internet.
It seems to be caused by trying to download an MMS. You cannot download MMS’s over the Internet – they’re not on there, they are on the cellular network. Moreover, I had actually turned off MMS downloading (never use it, so prevent accidents).
To prevent the popup message from appearing at random times, go to the Messages app, settings -> MMS, and uncheck “auto-retrieve” (or similar named setting).