Thanks to everyone who provided their inputs on this problem. It is not solved yet but now I created another problem so I guess the menuconfig will need a very detailed observation. Last time I had used the make menuconfig, clean, modules as well as modules_install so that was not a problem. The problem I feel is that by default the kernel supports ext3 journaling through module '<M>' instead of '<*>' so it gives an error of not recognising block (0,0) and cannot mount the fs on root=/dev/hdax. However even after setting it embedded, the new kernel now does not even go till the initial bootup messages. While repeating the process of 'make' I have got a lot of errors during compilation so I will do a clean retry and give feedback.
Are you sure you're not using an initrd? Because if you have an initrd.img in your directory tree then its quite likely that your stock kernel uses an initrd. If that is the case then you will need to build the ramdisk. Either that or run carefully through menuconfig and make sure that everything that you need (filesystem, critical drivers, etc.) are compiled in. ext2 and ext3 must be compiled into the kernel (with the [*] ). If your filesystem is anything else then you must cmpile that option into the kernel. For example I use reiserfs and have compiled reiserfs into the kernel.
Also, if you plan not to use the initrd, you must comment out that line from the menu.lst.
BG's suggestion of 'kernel-package' and the make-kpkg..... command was very usefull and I use that now. More feedback after some more results.
I think you have a 'make deb' option in the linux makefile that makes a debian package for your kernel. Never used it though. Always found the make install much more reliable, probably because I started with that approach and stuck with it all through. To find out all of the things you can do with the make command in the linux kernel source just do 'make help'.
Siddhesh