Hello All,
I was with Krish when he mentioned that he had successfully got multimedia playback in Ubuntu, by adding some repositories manually in the apt sources list and downloading extra packages.
When I got back, a google search revealed this page below and that finally did it.
http://www.ehomeupgrade.com/entry/2663/how-to_get_full
This explains everything in a simple and straightforward way. As I use Kubuntu, in the line
'sudo apt-get install totem-xine totem-xine-firefox-plugin libxine-extracodecs flashplugin-nonfree msttcorefonts sun-java5-plugin skype banshee streamtuner xmms realplay f-spot'
The 'totem-xine totem-xine-firefox-plugin' entries were removed as they are for Gnome and apt throws errors.
The important package is libxine-extracodecs.
I am now able to play VCDs with sound. My DVD freezes at the introductory text itself but that could be due to bad media or my DVD writer is country locked. Anyway now I am quite happy with the progress and hope others who were tearing their hair over multimedia in Debian based distros will find some relief from the link above.