Since 1.31.5 you need to actually have a province in the new world. Merely discovering it and having the Quest for the New World idea is not sufficient.I haven't actually checked the requirements; did they change them? It's pretty wild if no European has managed to even discover new world sooner.