So, I wonder it maybe my NAT problem. But after I installed my game on my friend's laptop which uses the same network I am using, I realized the MP works fine on his laptop. We both use Win7 and with the firewall on. What makes the difference?
Then I opened my virus scan program McaFee. You can't simply turn off this program in your system, BUT you can turn off its functions. So, with every function and scan off. I tried the MP again, fingers crossed.
It WORKed!!!! No more Check connectivity messages and I can play games without any problems.
Try this too, especially if you are in university areas.
Firewall or your router won't do any bad as long as you allow Crysis 2 to run in your system.
Hope this can help some people who were having the same problem I had for 3 weeks:)