Funziona se lo fai...
SYS.DBMS_AQ
anziché solo
DBMS_AQ
Se è così, ti manca un sinonimo.
MODIFICA :
Se ora stai ricevendo "PLS-00201:identificatore 'SYS.DBMS_AQ", controllerei due volte le tue sovvenzioni.
GRANT EXECUTE ON SYS.DBMS_AQ to <your-user>;
Inoltre, solo per confermare, hai concesso il privilegio di esecuzione direttamente all'utente e non tramite un ruolo?