Around the time of Columbus, were there other failed attempts?

England

The city of Bristol was the hub of English expeditions into the Atlantic. Several voyages were launched from her harbours, the second largest in England, around the time of Columbus. Bristol's mariners were inspired by the legendary phantom island of Brasil, which is said to lie off the western coast of Ireland⁽¹⁾.

There is some evidence^[2] that at least some attempts did reach Newfoundland, but many voyages were indeed failures. The Itineraria Symonis Simeonis et Willelmi de Worcestre recorded an early (supposedly) failed attempt by the author William Botoner's brother-in-law, John Jay:

1480, on July 15, the ship of John Jay the younger, of the burden of 80 tons began a voyage from the port of the Kingrode of Bristol to the island of Brasylle in^[3] the western part of Ireland, to traverse the seas ... and news came to Bristol on Monday the 18th of September that in the said ship they sailed the seas for about nine months, and did not find the island, but were driven back by storms to a port in Ireland for the refreshment of the ship and the men.

_{- Williamson, James Alexander. "The Voyages Of The Cabots And The English Discovery Of North America under Henry VII And Henry VIII. London: The Argonaut Press, 1923.}

Undeterred, the next year John Jay and another local merchant, Thomas Croft, launched a second expedition with two ships. Croft was later charged in connection of this voyage for shipping salt illegally, but exonerated on the grounds that he was exploring, not trading. The Court of the Exchequer noted in its proceedings that:

It is found amonges othir thynges that Thomas Croft of Bristow Squier on' of our Customers in oure said port of Bristowe ... shipped and putt xl bushhels of salt to the value of xxs. for ... not by cause of merchaundise but the entent to serch and fynd a certain Isle callid the Isle of Brasile as in the said inquisicion annexed to the forsaid commission more plainly it dothe appier.

_{- Carus-Wilson, Eleanora Mary, ed., The overseas trade of Bristol in the later middle ages, Bristol RS, 7, (1937)}

Officially this expedition also failed. However, given the cargo of salt, it has been theorised that that their goal was in fact fishing^[4]. Some historians have posited that the expeditions were in fact successful in finding Newfoundland, but kept the discovery secret in order to monopolise the new fishing grounds.

Alternatively, Alwyn Ruddock (famous for a book she never published) suggested that Bristol's mariners had accidentally reached Newfoundland in the past. Her theory is that these two voyages were unsuccessful attempts to rediscover those fisheries.

More instances of failed expeditions can be inferred from the letters of Pedro de Ayala, the Spanish envoy to England. He reported in 1498 that Bristol had sent several caravels into the Atlantic before discovering land "last year":

For the last seven years the people of Bristol have equipped two, three, four caravels to go in search of the island of Brazil and the Seven Cities according to the fancy of this Genoese. The king made up his mind to send thither, because last year sure proof was brought to him they had found land.

_{- H.B. Biggar ed., The Precursors of Jacques Cartier, 1497-1534 Ottawa, 1911, p. 28-9.}

However, having only just transferred to the Tudor court from Scotland, it could also be the case that his intelligence on Bristol weren't the most accurate.

Finally, John Cabot, the discoverer of North America in the conventional account, also experienced a failed first voyage in 1496. John Day, a Spanish spy in England, reported to a certain Lord Grand Admiral (possibly Columbus) in 1497 that:

Since your Lordship wants information relating to the first voyage, here is what happened: he went with one ship, his crew confused him, he was short of supplies and ran into bad weather, and he decided to turn back.

_{- Williamson, Williamson, James Alexander. The Cabot Voyages and Bristol Discovery Under Henry VII. Cambridge University Press, 1962, 212-214.}

Portugal

As is well known, Portugal's attention was preoccupied by Africa during this time. Still, there were sporadic westward interest. The most notable involved João Vaz Corte-Real. He was part of a joint expedition into the Atlantic by the Kingdoms of Portugal and Denmark, who were allies by marriage ties. They may have discovered North America following the routes of the Vikings of old:

In 1470, Afonso V of Portugal proposed to Christian I of Denmark that there be a joint Dano-Norwegian/Portuguese voyage of exploration ... The Danish captains with the expedition were Diderik Pining and Hans Pothorst, two privateers who had fought the English in the 1467 war over Icelandic fishing rights. The Portuguese sent several participants, including Corte-Real.

_{- Allen, John Logan, ed. North American Exploration. University of Nebraska Press, 1997.}

It is claimed that they reached Labrador and Newfoundland, which they called Terra do Bacalhau, Land of the Codfish. However, Pining, Pothorst and Corte-Real's purported discoveries are rather controversial. Therefore, it may or may not count it as "failed attempt" depending on which version of the events you are inclined accept.

Notes

(1) Or Portugal, or both Ireland and Portugal.

[2] In his 1497 letter, John Day, reporting on the John Cabot's discovery of Newfoundland, wrote of the discovered land that:

It is considered certain that the cape of the said land was found and discovered in the past by the men from Bristol who found 'Brasil' as your Lordship well knows. It was called the Island of Brasil, and it is assumed and believed to be the mainland that the men from Bristol found.

_{- Williamson, Williamson, James Alexander. The Cabot Voyages and Bristol Discovery Under Henry VII. Cambridge University Press, 1962, 212-214.}

[3] i.e., "the island of Brazil beyond the western part of Ireland."

[4] The coasts of Newfoundland and Northeastern America in general were excellent fisheries with significant commercial value well into the early modern era. Fish caught would be salted and dried on the islands before being shipped back (the reason why France retained Saint-Pierre-et-Miquelon in the Treaty of Paris, as late as 1763).