I've had the same problem - I'm in the UK with a US copy of MK, and the DS just doesn't find the g604t. I tried d-link support last night without much luck, part of the reason I bought d-link instead of netgear was at the time their phone support was still UK based, I think this may now have changed! (something like, me: 'there are many posts on forums with people having the same problem with this specific router'.... 'so your other wireless pc's work?'... 'it must be a problem with this computer'... me: 'but it's not a computer it's a games console - the nintendo ds'.... 'it must be because of this linux'... me: 'no the nintendo doesn't use linux, thats my other pc's and they are working fine'... 'we can't help this linux'.... me: 'the Australian version worked after a firmware upgrade, could I use the australian firmware'... 'NO! you must only use fiormware for your region'... me: 'I think you have failed to grasp what i'm saying, this service officially launches at the end of the week in the UK, *many* more people will contact you then with the same problem, i'll call again when you have recognised that there is an issue with this router'.... 'ok')
Anyway, feeling reckless I tried the EU firmware, but it would not install (i got the 'no magic number' error), so then I did the only thing d-link support were certain i shouldn't do and installed the Australian firmware (v2.00B02,
http://www.dlink.com.au/tech/drivers/files/routers/dslg604t.htm ). I had to use the 'corrupt install' tickbox, and I really thought it may be dead when it sat with a stationary progress bar for a couple of minutes, but eventually it installed. I changed my network settings to connect to it (it defaults to 10.1.1.1, instead of the UK versions 192.168.1.1), then had to set up all the ADSL settings more manually than usual (so note them down before hand!).
Next I tried the DS, and surprise surprise it worked, detecting it first time.
So, in summary, my g604t (UK model) is now running the .au firmware (Firmware Version : V2.00B02.AU), it's working fine with BTOpenWorld ADSL and on my network (wired and wireless connections) and it is now detected by the DS. However, upgrading to the .au firmware seems a risky strategy, and I wasn't entirely confident doing it, also it claims that you cannot downgrade once you've upgraded - so doing this would be entirely at your own risk!