Eralier I posted (and deleted) about the Queue class not implementing ICollection from some research this is by design.
From: http://msdn2.microsoft.com/en-US/library/92t2ye13.aspx
"Some collections that limit access to their elements, like the Queue class and the Stack class, directly implement the ICollection interface."
If you look, the interfaces are also very different from each other in what they include. The generic one includes methods such as ... Add, Remove, and Clear which do not exist on the non-generic ICollection.
So conclusion .. Queue is correct but I have to say that having the generic and non-generic ICollections that represent completely different things is a bit confusing at best :-/