OK, so I figured this out.
To make it really short, my host machine is actually a hacintosh and so my network card driver was the culprit. I don't expect many people might find this helpful, but I will write what I did to resolve my problem anyway.
So I have a Gateway machine (Gateway FX Series FX6801-01 Intel Core i7 950(3.06GHz) 9GB DDR3) and I just couldn't get VMWare bridged network to work. It turns out that the network driver was what was causing the issue.
I installed the trial version of Parallels to see if I could get the bridged network to work on the guest OS. I had the same exact issue and I was 100% sure that my environment was the issue. Then, I started to dig into network settings of Mac OS X. I erased all the settings and recreated the network, but nothing worked. So I decided to look at driver. I tested one driver after another and finally I found that AppleRTL8169Ethernet driver from MultiBeast works perfectly in my environment.
I know my case doesn't apply to many people (well, maybe...), but I thought I'd share my experience here because I have spent so many hours trying to figure this one out.
Cheers,