おおぅ

OS X 10.8 and later—Dispatch objects (including queues) are Objective-C objects, and are retained and released automatically.

こんなことになっていたのか。。。てっきり GCD のオブジェクトはCの構造体だと思っていました。試しに ARC を NO にしてみますと

[queue release];

が通ります。そして dispatch_release() も使えます。