AAC support is provided by the external faac and faad libraries (for encoding and decoding). You should be able to find the packages in your repositories, but I don't know the exact names Fedora uses.
Edit: actually, now that I think about it, I'm not sure about vlc. It generally builds in support for its codecs. Still, it can't hurt to try installing faad anyway.
Edit2: Yes, I was correct the first time. vlc does use faac/faad.
http://wiki.videolan.org/Advanced_Audio_Coding