Just to be sure, when you teleported to all cities, did you wait a bit to allow time for characters to load?
Indeed I believe SE changed the way cities (and other area) are structured, now even though those area seems like 1 big seemless area, it is actually divided in a lot a sub area. You may be running after 1 person and see the person diappear (she zoned, even though there is no real zone here), if you follow here in the new zone, this person wont re-appear direclty, need to re-load.
It makes for somewhat faster loading of everything (or so I'm told).
My server, Figaro, is anything but dead, with a LOT of people on at any time during the day (pic for jp prime time)