Look in the samples directory for the nmqsput and nmqsget c# examples - these do exactly what you are after and are good working examples.
Looking at the code above, I do not think there is a problem getting the message, followed up by your comment that amqsputc failed to find a message as well. I think the problem is on the putting side.
This may sound a silly question, but how do you know the message is there. What is the curdepth after the put? Look at the queue status - are there any uncommitted messages? (One thing I've seen before is putting under a unit of work (syncpoint) and then not committing and then another application trying to get it.