Rumours suggest that Google will not be able to launch its music streaming service in time for the upcoming Christmas holiday period.
According to The New York Post, music labels are not sure whether offering users a "digital locker" is a good idea or not.
Under current plans, Google's new music service would allow users to purchase and store music on a cloud based "digital locker", that would allow them to access their songs from anywhere and stream music to any device.
The biggest concern music labels have is that users will be able to store both pirated and legal music on the locker.
NY Post sources claim that Google is busy convincing music labels to sign deals on the "digital locker" service and music downloads, which will be integrated into its search engine.
“What's been holding things up is that the labels will do downloads, but they need to know more about the locker service, and Google really wants to keep the two together,” one source said.