Update: So I opened a new world and immediately built up to a Floating Island. Spent about 15 mins there, no luck. However I just defeated the Wall of Flesh for the first time on my main world, I already had a "skyway" constructed to navigate across the world swiftly by railway. Before I even made it to the top of my ramp leading to my skyway a Wyvern popped out of nowhere and chased me. I slowed down just enough to keep it right behind me and killed it within about 10 seconds with Jester arrows from my bow since it was following in a perfectly straight line behind me. I went down and came back up and the same thing happened again right after. So yeah it looks like you have to defeat the Wall of Flesh and get the new mobs (including the Wyvern) Thanks for all the help though guys!