Unusual deadlock occuring
Try without the first BEGIN TRAN and last COMMIT TRAN. 

If you are using a stored procedure, the procedure itself already creates a transaction. 

Your transaction locks because of the following script:

//This select does a table scan, so I believe does X lock on all rows
Select a,b,c
From queuetable with(xlock, rowlock)
Where a = x


From what I see in the script, the with(xlock, rowlock) is not needed.

Try with the following script:

SET XACT_ABORT ON
SET ISOLATION LEVEL REPEATABLE READ

-- This select does a table scan, so I believe does X lock on all rows
SELECT a, b, c
  FROM queuetable
 WHERE a = x

DELETE queuetable
 WHERE a = X

-- Get oldest row - this is the deallocking query
SELECT TOP 1 a, b, c
  FROM queuetable
 ORDER BY b

-- Mark row to be processed
UPDATE queuetable
   SET c = processing
 WHERE a = y