¿Funciona si lo haces...
SYS.DBMS_AQ
en lugar de solo
DBMS_AQ
Si es así, te falta un sinónimo.
EDITAR :
Si ahora obtiene "PLS-00201:identificador 'SYS.DBMS_AQ", entonces verificaría dos veces sus concesiones.
GRANT EXECUTE ON SYS.DBMS_AQ to <your-user>;
Además, solo para confirmar, ha otorgado el privilegio de ejecución directamente al usuario, y no a través de un rol?
