A VPN does not guarantee anonymity from outside the private network. Those packets of information still have to get from you to the VPN gateway and vice versa, and that basically means TCP/IP routing between these two endpoints, so your computer must still know its IP address in the LAN it's currently connected to in order to receive the VPN packets, and the routing chain is still possible to trace as long as all the nodes respond to pings and tell you where they're sending the packet next (this is where an anonymous proxy does its thing; it acts as the front door for one or more other IP addresses, and won't tell anyone who is behind it). Location Services requests information from your device, which will transmit it through the VPN, but that information could still include your non-VPN IP address as assigned by your current local LAN.
In addition, Google Location Services asks for a relatively large amount of data that is widely available, VPN or not. For instance, it transmits the SSIDs of any wireless networks in range. If you're using cell-based internet, the device can transmit cell tower identifiers. Google then uses this information to triangulate your location. It's usually not as accurate as GPS, because there are fewer data points to work with, not all of which can be used by Google to identify a unique location, and because range data from these sources is more variable than the exact timing mechanisms used by GPS. However, given enough of this data regarding your surroundings, Google can figure your position out to neighborhood level at least. If you're within 10 feet of a WAP that is well known to Google (i.e. full bars on "Starbucks 4010 Public Wi-Fi") then your location pretty much is that WAP's location.