Did you replace the router after you updated your iPhone to 3.1.2 or 3.1 for that matter? 3.1.2 just came out a week or two ago. One thing that you could try as it fixed some other network related things is to reset the iPhone's network settings and rejoin your wireless network. I know you said you tried the different cyper options and such, but it may be worth a try.
General -> Reset -> Reset Network Settings
then redo your wifi config with the "best" cypher options you can ( WPA2, AES ). works fine on my 655 and I know that iPhone OS 3.1+ had some issues with wifi for some people until they fully cleared the network settings.
I had updated to iPhone fw 3.1.2 when it came out. I hadn't noticed any problems. I just bought the DIR-825 a couple of days ago.
I have not tried resetting network settings. Are you saying that you're successfully using your DIR-655 with an iPhone running 3.1.2 with WPA2/AES?
Latest things I've tried...
I'm setup the guest network on the DIR-825. Confirmed that it still fails with WPA2/AES.
If I turn off security completely... it seems to work fine. Did not experience a problem.
Now I've turned on 128bit WEP and so far so good, no problems.
This looks like it narrows the problem to WPA/WPA2 negotiation with the iPhone 3.1.2.
Update: I tried resetting network settings on the iPhone and connected to my network as auto WPA/WPA2, TKIP and AES. It failed after a while. I therefore have no reason to believe that resetting network settings helps.
The only thing I've found to work (so far) is either disabling security completely or using WEP.