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();