A single cognitive radio transmitter--receiver pair shares the spectrum with two primary users communicating with their respective receivers. Each primary user has a local traffic queue, whereas the cognitive user has three queues; one storing its own traffic while the other two are relaying queues used to store primary relayed packets admitted from the two primary users. A new cooperative cognitive medium access control protocol for the described network is proposed, where the cognitive user exploits the idle periods of the primary spectrum bands. Traffic arrival to each relaying queue is controlled using a tuneable admittance factor, while relaying queues service scheduling is controlled via channel access probabilities assigned to each queue based on the band of operation. The stability region of the proposed protocol is characterized shedding light on its maximum expected throughput. Numerical results demonstrate the performance gains of the proposed cooperative cognitive protocol.