I will try getting the dhcp-dns server. I have Ubuntu 7.04 on my laptop and with WinXP running on my desktop I am able to share internet connection with ubuntu (the dialup connection is now on the desktop), so I am a bit doubtful as I don't remember installing any dhcp server on my desktop.
I tried the static addresses thing, it shows that network is up, i can ping each of the machines from the other but, I am not able to access internet on Fedora(desktop). I set SELinux policies as permissive and switched off windows firewall just in case, but no luck.
Anyways I will try your suggestions and let you know. Thanks a lot.