I've ported the non-blocking queue psuedocode here to C#. The code below is meant as a near verbatim copy of the paper.

What approach would you take to test the implementation?

Note: I'm running in VS2010 so I don't have CHESS support yet.

using System.Threading;

#pragma warning disable 0420

namespace ConcurrentCollections
{
    class QueueNodePointer<T>
    {
        internal QueueNode<T> ptr;
        internal QueueNodePointer() : this(null) { }
        internal QueueNodePointer(QueueNode<T> ptr) { this.ptr = ptr; }
    }

    class QueueNode<T>
    {
        internal T value;
        internal QueueNodePointer<T> next;
        internal QueueNode() : this(default(T)) { }
        internal QueueNode(T value) { this.value = value; this.next = new QueueNodePointer<T>(); }
    }

    public class ConcurrentQueue<T>
    {
        private volatile int count = 0;

        private QueueNodePointer<T> qhead = new QueueNodePointer<T>();
        private QueueNodePointer<T> qtail = new QueueNodePointer<T>();

        public ConcurrentQueue()
        {
            var node = new QueueNode<T>();
            node.next.ptr = null;
            this.qhead.ptr = this.qtail.ptr = node;
        }

        public int Count { get { return this.count; } }

        public void Enqueue(T value)
        {
            var node = new QueueNode<T>(value);
            node.next.ptr = null;

            QueueNodePointer<T> tail;
            QueueNodePointer<T> next;

            while (true)
            {
                tail = this.qtail;
                next = tail.ptr.next;
                if (tail == this.qtail)
                {
                    if (next.ptr == null)
                    {
                        var newtail = new QueueNodePointer<T>(node);
                        if (Interlocked.CompareExchange(ref tail.ptr.next, newtail, next) == next)
                        {
                            Interlocked.Increment(ref this.count);
                            break;
                        }
                        else
                        {
                            Interlocked.CompareExchange(ref this.qtail, new QueueNodePointer<T>(next.ptr), tail);
                        }
                    }
                }
            }

            Interlocked.CompareExchange(ref this.qtail, new QueueNodePointer<T>(node), tail);
        }

        public T Dequeue()
        {
            T value;

            while (true)
            {
                var head = this.qhead;
                var tail = this.qtail;
                var next = head.ptr.next;
                if (head == this.qhead)
                {
                    if (head.ptr == tail.ptr)
                    {
                        if (next.ptr == null)
                        {
                            return default(T);
                        }

                        Interlocked.CompareExchange(ref this.qtail, new QueueNodePointer<T>(next.ptr), tail);
                    }
                    else
                    {
                        value = next.ptr.value;
                        var newhead = new QueueNodePointer<T>(next.ptr);
                        if (Interlocked.CompareExchange(ref this.qhead, newhead, head) == head)
                        {
                            Interlocked.Decrement(ref this.count);
                            break;
                        }
                    }
                }
            }

            return value;
        }
    }
}

#pragma warning restore 0420