The native resolution for your L2610NW is 1920 x 1200 and the Mac Mini supports that using the HDMI port.
With the monitor connected, reset the PRAM as per > About NVRAM and PRAM
1. Shut down the computer.
2. Locate the following keys on the keyboard: Command, Option, P, and R. You will need to hold these keys down simultaneously in step 4.
3. Turn on the computer.
4. Press and hold the Command-Option-P-R keys. You must press this key combination before the gray screen appears.
5. Hold the keys down until the computer restarts and you hear the startup sound for the second time.
6. Release the keys.
My advice is call Applecare since you should still be under warranty and possibly schedule a visit to an Apple store where you can bring both the monitor and the Mac Mini in and demonstrate the problem. I agree with you 100% this should work out of the box with no issue, especiallty since your wife's laptop had no issue.