Yes and no.

Mistlands will generate in areas where no one has explored within around 500m. That means if any of your friends went there it won't work right. If you have large unexplored areas on your map then it will probably work. If you go this route, your chances are better if you sail east or west, because ashlands and the north eat up the north and south.

On the other hand, map generation has changed with the new update and the Mistlands you get on an old map won't be as large and it may be harder to find one that isn't a bunch of rocks sticking up out of the water.

A new map is probably better but you might be able to make it work on an old one.