Usually this problem is associated with electromagnetic interference, but first make sure your XBOX 360 network card isn't damaged by moving the 360 close to the router and using another Ethernet cable. Also, are you connecting the 360 to a switch or router? If you've setup your network improperly over a switch, then you might not have enough public IP addresses available for your XBOX 360 to connect to the internet.
Usually testers only check for broken pairs, then don't check for EMI. Are you running the cable close to power lines? Are you running the cables over florescent lighting? There are many things that can result in a warped signal over the wire. If that signal is warped, then DHCP packets will not reach the XBOX 360 and you will not receive an IP address.