Nokia, the world’s largest mobile phone maker, has begun rolling out the Ovi store, its answer to Apple’s App Store.

Upon launch, the Ovi store was loading very slowly, and continues to.

It is available in some countries, but not others. Here in the U.S., AT&T will support Ovi Store, but timing for that U.S. launch hasn’t been announced yet.

Nokia’s big step forward with the store, as we’ve reported, is that it allows “direct billing,” where Nokia lets customers charge to their wireless account for each app downloaded, and give app developers a cut. Nokia has continued to say direct billing will be available in the U.S., despite some reports suggesting it may not. When I asked a Nokia spokeswoman today about it, she said billing options for ATT customers “are not disclosed yet,” which suggests the company must be working hard to iron out some final issues related to that offering, otherwise Nokia would just come out and announce it unequivocally.

VB Transform 2020 Online - July 15-17. Join leading AI executives: Register for the free livestream.

Application developers will probably love the new payment method. Until now, the main way for billing through wireless carriers has been the clunky “premium SMS”, where users have to pay first and then get what they want to buy.

Blogger Terence Eden took screenshots of problems he ran up against while trying to use the store. His conclusion: “Why do I get the feeling that there are several fiefdoms within Nokia all working against one and other rather than working together?” Eden has summarized his experiences in a second post: “Nokia Ovi – 25 Mistakes.”

We’ll continue posting Ovi Store reports. Add yours to the comments below, or just mail them to venturebeat@gmail.com.

Are you an entrepreneur or executive active in mobile? Join us at MobileBeat 2009, our mobile conference for industry leaders. Sign up by June 9 (we’ve extended the earlybird), and save $145.