When I was initially setting up my CentOS boxes I ran into a lot of similar problems.
RHEL and CentOS repos may be used interchangeably. With a degree of care even RHEL 5 repos may be used. When it comes to using these repos you need to use only a single external repository - either RPMForge, EPEL, etc. Mixing repositories creates a major problem. Also be sure to use the yum-priorties plugin.
When it comes to the packages listed with broken dependencies they can generally be removed and reinstalled to correct dependency issues. Just be sure to make a list of impacted packages. This is especially true for VLC - there were only about 4 or 5 packages impacted the last time I needed to do so.
My preferred repo is RPMForge. http://dag.wieers.com/rpm/FAQ.php#B
If you have been mixing repositories I highly suggest that you remove all packages from third party repos and start over. This can be done by either an OS reinstall or manually tracking down the packages. If you did not use yum-priorities to begin with your system is likely very broken and a reinstall would be the best solution.