Suggestions? Sure. Do something different to get your 360 onto your network. I believe the "NAT = strict" is coming, not from your router but from your iBook. You're running into the old and unpleasant "double-NAT" problem, where you have two different devices performing Network Address Translation, and XBox Live doesn't work well (if at all) with that.
For a long time, we had my son's 360 connected (straight to the router) via a very long Ethernet cable until he finally coughed up the money for a Microsoft wireless adapter for the 360. Why are you using the iBook to handle this connection?