Found the issue.
The issue wasn't with the patch (well kind of is)
My xbox was set on Automatic IP retrieval, where as my brothers was set on manual.
I applied the patch, and my NAT was then OPEN, but my brothers remained STRICT.
I then changed my brothers to automatic, and boom - open NAT.
The only possible reason I can think of, is that because I applied the patch while his xbox was connected, it for some reason didn't apply the port forwarding to that specific address.
Other than that, I can't understand any other reason why it shouldn't have worked.