Google Music, a download music store that would include à-la-carte purchases as well as a subscription component, has been in the works for over a year. Most of that time has been spent discussing a deal with top publishers and the four largest record labels, but the latest information suggests there has been little progress, according to All Things Digital.

Google's negotiations with the big music labels are "broken," says a source familiar with the search giant's thinking: "There's definitely a problem with the Google music conversations." Another industry source says Google's top executives are reconsidering their music plans altogether. "They've gone backwards," I'm told.

Some label executives are unaware of this new development, saying they thought negotiations were progressing smoothly and that they felt confident they would strike deals with Google soon. Others contend that Google has changed its terms in the past few weeks and that has held up negotiations.

This news follows information from last month that Google employees had begun testing Google Music internally, suggesting that the service was almost ready. This may still be true, but if the search giant can't get the music labels onboard, it's going to have a very difficult time offering something competitive to Apple's iTunes.

All this news is still technically conjecture and speculation based on sources close to the company and the music industry. Google has still not announced its music initiative publicly, though many expect it to show off at least a sneak peek next month at its Google I/O 2011 conference, which is taking place on May 10, 2011 and May 11, 2011.

A rumor from September 2010 originally suggested Google Music would allow consumers to purchase music by the track or album, and also pay $25 per year to store songs in the cloud. Amazon already beat Google to the punch on the latter when it launched Cloud Drive last month.