I can't address speeding it up.
You have found another mistake I've made. Thank you
To make this test go faster I will only check the 9 tuple that should pass.
testallperms[three_]:=({n1,n2,n3,n4,n5,n6,n7,n8,n9}=Flatten[three];
Union[Table[{n1,n2,n3,n4,n5,n6,n7,n8,n9}=NextPermutation[{n1,n2,n3,n4,n5,n6,n7,n8,n9}];
If[x==n1^2+n2^2+n3^2==n4^2+n5^2+n6^2==n7^2+n8^2+n9^2==n1^2+n4^2+n7^2==
n2^2+n5^2+n8^2==n3^2+n6^2+n9^2==n1^2+n5^2+n9^2,
{n1,n2,n3,n4,n5,n6,n7,n8,n9},Nothing],{9!}]]);
testallperms[{29,41,23,1,37,41,47,1,29}]
and that does, hopefully correctly this time, return
{{29,41,23,1,37,41,47,1,29}}
I apologize for my mistakes.
I am a little concerned about the use of three Select functions in the code, where one of those seems to be looking for lists of length greater than or equal to seven, when Length[Union[{29,41,23,1,37,41,47,1,29}]] returns 6. But the code seems to be accepting your list and I don't believe I wrote those Select functions that way.