Reding told the Guardian on Thursday that "we aren't playing games here", while suggesting Google was trying to "sneak" users' privacy away.
Google moved to the new policy on Thursday, allowing it to link up user data from various services such as search, YouTube and Gmail. The shift means, for example, that the user's choice of YouTube viewing may help shape Google Search results or the ads shown in their Gmail.
As long as users are logged into any Google service, they will not be able to opt out of having their data shared in this way.
The French privacy watchdog CNIL, acting on behalf of EU data protection authorities, has come to an initial conclusion that the move breaks European data protection law, and has pleaded with Google to pause its program — to no avail.
"Any company which wants to utilise the European market of 500 million citizens — which we've made borderless, a golden opportunity — then the European rules apply," Reding said on Thursday, adding that the EU's data protection authorities were "deeply concerned" about the situation.
Reding is in the process of bringing in a new Data Protection Directive for the EU, which has already got her office at loggerheads with Google.
Google says the reforms — specifically the new 'right to be forgotten' — are not suitable for search engines and hosting platforms. Reding's office has countered that the proposed rules take such business models into account.
Google is also embroiled in the early stages of an EU antitrust probe, following complaints by rivals over search and other policies.