Я вижу два очевидных варианта:
[queue cancelAllOperations];
или, если вы хотите больше контроля:
[request cancel];
для каждого запроса, который вы хотите «удалить» (это технически не удаляет их, но может иметь достаточно близкий эффект для ваших целей).
Хотя, я думаю, [queue reset];
также должно работать - может быть, вы можете точно объяснить, что происходит, когда вы пытаетесь его использовать?
Если ничего не помогает, освобождение и повторное создание очереди должно удалить все.
Обновление
Для дальнейшего объяснения, я не думаю, что на самом деле возможно удалить элементы из NSOperationQueue, только чтобы отменить их. (ASINetworkQueue является подклассом NSOperationQueue.)
Документы по яблоку здесь:
http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/NSOperationQueue_class/Reference/Reference.html