The rebranding occurred when Google changed it from an Android app store into a one-stop-shop for apps but also books, movies, and other downloadable media.
I took it as a way of making Google's involvement more clear; it's not immediately obvious "Android Market" is Google-related, where "Google Play Store" is.
I've been thinking more about this, and it's strange that Microsoft also rebranded their Windows Phone Marketplace to Windows Phone Store. Makes me wonder if focus groups don't like the word "market" for some reason. It's not commonly used in Americanized English, so I wouldn't be surprised if many people are confused by what Market is, in terms of a phone application.