Revamped, legal business model? Check.

Glitzy new Web site? Check.

Promised access to more than 25 million songs? Check.

Signed agreements to actually deliver that access?

Hold please.

Qtrax, the former P2P file-sharing service that morphed into a free, legal, and ad-supported music service, launched with a beta version over the weekend to much fanfare at the Midem conference in Cannes, France. But according to the major labels from whom they would need to license the bulk of the music for the service, they spoke too soon.

Qtrax told Reuters that it had deals with the major labels representing about 75 percent of all music sales. But today, Sony BMG Music Entertainment and Warner publicly denied that they had agreed to back the new Qtrax service

And the world's largest music company, Universal Music Group, reportedly had not yet signed a deal either, while a deal Qtrax inked with EMI was only with its song publishing unit, not its recorded music division.

The primary source of confusion appears to center on Qtrax's decision to alter its business model last year and the fact that it had endorsements but no signed agreements for the revised model, according to the labels.

The free, ad-supported model has gathered mixed reception from the major labels to date. As previously reported, Last.fm now has major label support for its service, which allows three free streams of a song before being prompted to buy that song.

The labels have also licensed music to iMeem, which incorporates allows users to send each other tracks for streaming and download. SpiralFrog, an ad-supported music rental service, has struggled to sign any other major record company since launching last September with music from Universal Music.

Qtrax has not publicly clarified the licensing confusion but did issue a statement promising more news to come.

"The response to the service is clearly unprecedented. We launched at Midem, the leading music industry conference, precisely because of the degree of support we have had and continue to enjoy from rights holders," Qtrax CEO Allan Klepfisz said in the statement, which focused on users unable to get access to the songs promised at launch. "We believe the exact nature of that support will be publicly clarified within a very short time. As the world's first free and legal P2P service that has chosen to spend 4.5 years on licensing and not to violate IP rights, we have decided that we will provide activation keys shortly upon final execution of all pertinent contracts."