Well I do not know., what you do, but getting columbus only halfway across is quite a feat.
He has a rating of 6 for navigation (the first one) and so can stay 12 month out in the sea without suffering any attrition. adding a few more before three ships are gone through attrition, that gives you 18 month. thats enough to sail straight west until you find the carribean, explore to sea zones there and return with one or two ships. Of course you need to start from Gran Canaria and do not stray from the path to much.
Finding a land area in the first try is a question of luck (I would say about 50% if you explore 3 sea zones), but if it fails you just come back next year. And remember to have a few ships ready for him, to take care of the attrition losses.
Ciao
Kulko