There is some good information here http://arduino.cc/forum/index.php/topic,68816.0.html if you follow the links in the post.
This bit of info relates to the pull up resistors specifically
Aside from the obvious (wrong pins and no pull up resistors) Are you sure both ends are operating ath the same voltage either bothe at 5v or both at 3.3 v ?