From MSDN:
A Queue<(Of <(T>)>) can support
multiple readers concurrently, as long
as the collection is not modified.
Even so, enumerating through a
collection is intrinsically not a
thread-safe procedure. To guarantee
thread safety during enumeration, you
can lock the collection during the
entire enumeration. To allow the
collection to be accessed by multiple
threads for reading and writing, you
must implement your own
synchronization.
You should ensure no reader is active while an item is queued (a lock is probably a good idea).
Looking at the count in reflector reveals a read from a private field. This can be okay depending on what you do with the value. This means you shouldn't do stuff like this (without proper locking):
if(queue.Count > 0)
queue.Dequeue();