Apple Inc.’s (Nasdaq: AAPL) map-software shortcomings – though vexing for many iPhone owners – have been a boon for makers of competing mobile-navigation tools.

AOL Inc.’s MapQuest leaped into the top 20 on Apple’s App Store, while start-up Waze Inc. said its downloads hit a record today after Apple Chief Executive Officer Tim Cook suggested Friday that customers frustrated with his company’s iPhone mapping software try services from a competitor.

Apple also opened a navigation category within the online App Store.

The boost came after Cook issued a public apology for inadequacies with its “Maps” mapping software introduced last week. The tool has been widely faulted for unreliable landmark searches, routes that get users lost and a lack of public transit directions. The new mapping replaces Google Inc.’s service, which had been Apple’s default navigation tool since the iPhone was introduced in 2007.

“This is going to be our biggest day ever,” Noam Bardin, CEO of Palo Alto, California-based Waze, said in an interview. “I can’t even predict where it’s going to end.”

Cook singled out Waze, MapQuest and Microsoft Corp.’s Bing as alternatives to Apple’s mapping application that can be downloaded from Apple’s App Store. He also said mapping services from Google and Nokia Oyj could be used from the iPhone’s web browser.

“At Apple, we strive to make world-class products that deliver the best experience possible to our customers,” Cook said in a statement posted on the company’s website. “With the launch of our new Maps last week, we fell short on this commitment.”

Google’s Head Start

Microsoft said it didn’t yet have data to report on the number of Bing downloads.

Since introducing the mapping application last week as part of a mobile-software upgrade, Apple has been learning how difficult a service navigation is to provide, Bardin said. Google and Nokia are two of the biggest mapping companies, along with TomTom NV, from which Apple is licensing data.

Apple introduced the new feature to replace Google, a business rival that makes the competing Android operating system used by companies including Samsung Electronics Co.

Google started its mapping service in 2005 with mixed results. Yet it grew to become one of the industry leaders by investing heavily and sending out cars loaded with Global Positioning System sensors and other technology to map the world.

User Help

To catch up, Apple will rely on the millions of iPhone and iPad owners. Cook said that more than 100 million people are using the company’s new iOS 6 mobile operating system with the new mapping software. As more people use the service, data will be accumulated that can help improve it, he said. The application has a feature for customers to tell Apple when there’s a bad location or other bug.

Bardin of Waze said he was thrilled to be mentioned in Cook’s apology letter. His company offers a free crowd-sourced navigation tool, so that any time somebody uses the service they are passively sending GPS data back to the company that is used to build better maps. It can alert drivers to traffic and divert them to different routes, based on data being sent from smartphone owners up the road.

“The more people who use my service the better it is,” said Bardin, whose company is funded by investors including Kleiner Perkins Caufield & Byers. The company plans to make money eventually by selling location-based advertisements.

Apple is being held back because the underlying data it’s licensing isn’t good enough, Bardin said. While the quality will improve, it will be very expensive to match the sum Google has already spent on maps, he said.

“The tactical challenge is they bit off what Google does really well,” he said, “and tried to do it themselves.”