I don't have El Dorado, was playing as Castile (nice easy way to try out the new machanics), got an event that gave me Columbus. "Hurrah!" thinks I, "let's get started early on the New World". Unfortunately, "you can't cross oceans as you don't have Quest for the New World", so I explored all around Africa to India but I can't sail past the Cape Verde Islands and go see what's across the ocean blue...
However, I can confirm that colonisation is still screwed without El Dorado - the aforementioned islands had not been colonised by Portugal and I can't colonise them either, as they show as "this is too far away" despite being well within range from the Canaries (and yes, I'm at peace and they're not blockaded or under rebels or anything).
As other people have mentioned, seems that the "colonial distance" calculation is a teensy bit screwed at the moment. So, fingers crossed for the beta hotfix....

(and in the meantime I'm going to have another super-easy play in the sandpit as the Ottomans and not have to worry about the New World for ages)
Random thought - has anybody tried 1.13beta with Random New World, and does the same happen there...?