We present a novel cross layer approach to random access (RA) that combines physical-layer network coding (PLNC) with multiuser detection (MUD). PLNC and MUD are applied jointly at the physical level in order to extract any linear combination of messages experiencing a collision. The set of combinations extracted from a whole frame is then processed by the receiver to recover the original packets. A simple pre-coding stage at the transmitting terminals allows the receiver to further increase system diversity. We derive an analytical bound on the system throughput and present simulation results for the decoding at the physical level as well as several performance measures at frame level in block fading channels, namely throughput, packet loss rate and energy efficiency. The results we present are promising and suggest that a cross layer approach leveraging on the joint use of PLNC and MUD can significantly improve the performance of RA systems.