In vehicular ad hoc networks (VANETs), safety messages must be protected for location privacy. Pseudonym schemes have provided a promising solution. However, attacks could still be carried out from the medium access control (MAC) layer. In this paper, we present a new MAC semantic linking attack that links the new and old pseudonyms by analyzing the vehicles' transmission patterns in the MAC layer, even if they change pseudonyms simultaneously. To deal with the attack, a MAC layer aware pseudonym (MAP) scheme is proposed. The MAP scheme is compatible with the standard and coordinates each vehicle to access the wireless medium in a time-slotted manner. In MAP scheme, vehicles change pseudonyms and slot utilization pattern consistently. The interactive influence between the pseudonym changing and safety message transmission is evaluated. Taking the pseudonym age, anonymity set size, time-toconfusion and packet delivery ratio as the performance metrics, extensive simulation results have verified that the MAP scheme can improve the location privacy and enhance transmission efficiency in VANETs.