Although I couldn't find any fix for this problem, I decided to give Minitube another try even though it too had similar issues in the past which is the reason I switched to Gmediafinder.
Since then Minitube 1.8 has been released and a fix for it was posted which basically requires more restricted extras to be installed and renaming the libgstvideoparsersbad.so plugin.
Apparently the libgstvideoparsersbad.so plugin has a bug that creates a problem with the playing videos and the person who posted it didn't explain why, but I guess it doesn't really matter just as long as it fixes Minitube.
Before installing minitube, you must first install the plugins followed by renaming libgstvideoparsersbad.so.
(1) Install Plugins:
sudo apt-get install libqtgui4 libqt4-xml libqt4-network libqt4-dbus phonon-backend-gstreamer gstreamer0.10-ffmpeg gstreamer0.10-plugins-bad
(2) Rename libgstvideoparsersbad.so:
sudo mv /usr/lib/i386-linux-gnu/gstreamer-0.10/libgstvideoparsersbad.so /usr/lib/i386-linux-gnu/gstreamer-0.10/libgstvideoparsersbad.so.bak
(3) Install minitube
sudo add-apt-repository ppa:ferramroberto/minitube
sudo apt-get update
sudo apt-get install minitube
After I followed these steps I'm now able to play videos just fine.