With the new update on Jan 18 2012, Foursquare has moved their add venue option from Check In screen. I was thinking that they have removed this option at all. But that is not so. You can add new venue but first you need to search that venue, and at the end of the listing you will find the option to add new one.

They must mention this change in their release notes. Since this change, a lot of people crying over their Android market page that where the hell this option is.

Enjoy check ins!