I still had this problem with a recent distribution of AUCTex, so I looked for an answer. The one given here did not solved my problem. Yet, I added the following command to my .emacs file and everything went fine:
(setq LaTeX-verbatim-environments-local '("minted"))
I hope this might help some people.