A mobile station executed method, wherein upon changing from a current cell to a new cell in a wireless packet data network the mobile station enters the new cell; generates a cell change packet data unit (PDU) message for informing the network of the location of the mobile station in the new cell; buffers the cell change PDU message into a PDU transmit queue before any buffered PDUs that were present before the mobile station entered the new cell; and transmits the buffered cell change PDU before any of the buffered PDUs that were present before the mobile station entered the new cell. In accordance with another method for informing the wireless network of the MS cell change, the following steps are executed: (i) in response to the MS making access in a new cell, sending a Channel Request that indicates a Cell Update operation; (ii) establishing an uplink (UL) Temporary Block Flow (TBF) for transferring Logical Link Control (LLC) Packet Data Units (PDUs) from the MS to the network; (iii) in response to the network receiving an unknown Temporary Logical Link Identifier (TLLI) from the MS, sending a message to a Serving GPRS Support Node (SGSN) and (iv) based on the message, determining with the SGSN the new cell location of the MS.