Est-ce que ça marche si vous faites...
SYS.DBMS_AQ
au lieu de simplement
DBMS_AQ
Si c'est le cas, il vous manque un synonyme.
MODIFIER :
Si vous obtenez maintenant "PLS-00201 :identifiant 'SYS.DBMS_AQ", je vérifierais vos subventions.
GRANT EXECUTE ON SYS.DBMS_AQ to <your-user>;
De plus, juste pour confirmer, vous avez accordé le privilège d'exécution directement à l'utilisateur, et non via un rôle ?