The VLC app is now coming from fedora and it previously was installed from rpmfusion.
It seems some of the codecs it earlier required are no longer installed automatically because of the restrictions fedora has on what it may distribute.
Try installing ffmpeg and/or libavcodec-freeworld from rpmfusion while using dnf. The command would be something like sudo dnf install ffmpeg libavcodec-freeworld --allowerasing as long as you have the rpmfusion-free repo enabled.
I have both those installed though some seem to only use ffmpeg.