I see the thought there but here is the rub (counter to that argument): The router, in most cases hasn't changed. There should not be any reason why a router would block certain types of communication. Plus, the issue persists over multiple Wifi sources. Since the Wifi does work for other Internet services such as web browsing, email, etc, its safe to say that Wifi communication in Marshmallow does work.
My thought is since all IP based services work over TCP or UDP ports (eg 80=WWW, 25=SMTP), Google Play Store must use a port number for either incoming download or outgoing download requests (one thought would be FTP 20/21), perhaps Marshmallow is blocking or has a programming issue with the port Google Play Store operates on.
I searched the known ports: Google Play Services (eg Play Store) operates on 5228. I wonder if one can verify that Marshmallow does or does not allow that port or any return port back to Play Store. Destination ports have a source port associated with IP based communication.