Having the same, issue, got the jet boots upgrade, found a portal gun, so I'm traveling realy fast but I'm not finding a single village, zero, none. I have yet to find a neather fort too, and I have coverd ALOT of terrain. By now I must have raided like, 10+ burial mounds, 20+ wisp spawning thingies, a pyramid, a few jungle temples... a witch hut, found two abandoned mines, some dungeons.
Maybe I'm traveling to fast for them to generate properly? But seriously, this is getting silly. I have only ben able to get emeralds from lootbags and dungeon chests and I haven't had the luck to find any blaze rods.
*and I'm using default world generation. Maybe natura is messing with things?