I really really appreciate the help extended by all the friends here. Special thanks to Mr. Nick Gammon. Your solution worked like a charm sir.
It comes out that I was using wrong pins of Mega to connect to duemilanove. This should have been explained by arduino guys while explaining how to use Arduino as ISP. Thanks to Mr. Gammon, I used the mega pins as he explained and followed the instructions given at http://www.sparkfun.com/tutorials/247
I was able to successfully program both the new Atmega328p and they are taking up sketches as they are supposed to.
A word of caution though, for newbies like me: Avrdude does not work properly with IDE 0018. while worked perfectly with IDE 1.0. Also, the bootloader for 328p that comes with "Arduino Optiboot Bootloader" ( which can be downloaded at the sparkfun page linked above) did not work for me. It burned the bootloader but then I was unable to upload sketches to 328p. Contrary to that, the bootloader that comes arduino IDE, works perfectly fine.
@CrossRoads: do we need to set fuses first for the new part for using optiloader to program directly through mega?