If you ever have a really tricky bug, try printing out the entire source repo on origami paper and laying out the sheets in a Hilbert curve pattern on the floor. Then throw out some silicium sticks -- one for each thread you were running -- and 63% of the time, one will land on the buggy line of code.
It turns out the problem was that in main() just before I called queueConstructor, I added the item 633346 as an integer element in my stack data structure. Whether this overflowed the integer, I don't know. But I don't know why it would stop malloc for a different data structure stored in a different variable from working (perhaps it was occupying some memory that my queue wanted?).
This isn't the first time bugs like this happen, and as a novice programmer I really wish tools were better, or I knew how to use the tools. GDB available via CodeBlocks wasn't helpful.
My first suggestion would be to familiarize yourself with valgrind to make sure that you aren't accessing memory that you shouldn't be. Next would be writing tests so you can isolate problems like this.
When you've got 58 different systems interacting you'll occasionally come across some weird problems that you can't replicate, but they should be few and far between.
A really tricky bug, back to first principles and science, then work back from there.
By the way - I work with underground services....
Not too surprising considering what we know about Buffon's needle.