After listening to a internet radio stream for a while playbin2 blocks. Looking into it with gdb revealed the following (only the relevant parts pasted):

+ Trace 193141

Looking into the gstqueue2 at the relevant lines showed that the waits are respectively for removing/adding a queue.. So it's both waiting for an item to be removed and to be added.. Using gdb to doublecheck:

(gdb) p ((GstQueue*) 0x76a020)->waiting_add
$48 = 1
(gdb) p ((GstQueue*) 0x76a020)->waiting_del
$49 = 1

Woopsie.. So let's see if it's actually empty:
(gdb) p ((GstQueue*) 0x76a020)->queue->length
$50 = 0

Apparently it is. So now let's see why it thinks it's full:

(gdb) p ((GstQueue*) 0x76a020)->max_level.buffers
$65 = 100
(gdb) p ((GstQueue*) 0x76a020)->cur_level.buffers
$66 = 0
(gdb) p ((GstQueue*) 0x76a020)->max_level.bytes
$67 = 2097152
(gdb) p ((GstQueue*) 0x76a020)->cur_level.bytes
$68 = 0
(gdb) p ((GstQueue*) 0x76a020)->max_level.time
$69 = 2000000000
(gdb) p ((GstQueue*) 0x76a020)->cur_level.time
$70 = 0
(gdb) p ((GstQueue*) 0x76a020)->use_rate_estimate 
$71 = 1
(gdb) p ((GstQueue*) 0x76a020)->max_level.rate_time
$72 = 2000000000
(gdb) p ((GstQueue*) 0x76a020)->cur_level.rate_time
$73 = 2015175107