Whether alone (with user movement and precise clocking) or in a coordinated group effort, devices might begin to triangulate tower location and check this against historical and geographic data.
It would be a bit ironic, if/when triangulation begins to "work" "in the other direction".
It already is: Mozilla has been building apps¹ that allow users to contribute to a shared database of the locations of cellphone towers and WiFi APs.
The idea is to allow GPS-less devices to find where they are, but it could certainly be used to identify new towers in places which had already been mapped.
EDIT: It seems there's also opencellid.org, which actually allows you to download the full database.
3G provides some cryptographic basis for this, but you might not have a UI on your device to require 3G or to warn you about roaming (which could defend at least against early generations of IMSI catchers).
a) a new cell tower ID has suddenly appeared at a specific lat/long when it wasn't there before
b) the encryption/protocol changes or gets degraded
[1] https://secupwn.github.io/Android-IMSI-Catcher-Detector/