Uninstall Parallels, using the uninstaller if there is one, and all the Windows files that go with it.
Run Repair Permissions from the Disk Utility. (After the uninstall)
If this fails to correct the problem, try an Archive and Install using the Mac Mini Restore disks that came with the computer.
Let us know how you get on
I have a Mac Mini Intel chip model about 1.5 years old with 10.5.1 Tiger OS. At home I use wired ethernet - router - DSL and have no problems exchanging files with another Mac and two other PC's on my network. I installed Parallels, but never activated or used it so far. I also installed open DNS to experiment with Internet control without using a filter program.
I now have brought my Mac on the road with me and had no problem connecting with wired internet in my first hotel location.
I opened the system settings and when clicking on the Network icon, got a dialog box that in the background shows Parallels running and no connection via the built in Airport wireless. A popdown menu with the message "Your network connections have been changed by another program" appeared and no matter how many times I clicked the OK button it won't go away and let me reconfigure any network settings.
Leaving it in the background, I was able to use the Mac and even the wired internet connection worked fine.
The system refused to shut down normally because the dialog box won't close and go to the next step. Had to force shutdown by holding down the power button.
Now when trying to use the Airport in another location without wired internet and the same condition is still present. Now HAVE to fix it. Clicking the Airport icon on the menubar at the top in the Finder opens the submenu to allow me to turn ON the Airport, but their network doesn't appear. When opening the network icon from the system settings, we are back stuck with the popdown message that won't get out of the way.
Turning OFF Open DNS so it doesn't load on startup had no effect. There is an icon on the top menubar that shows when it is running, and I have the utility installed that shows all threads and how much processor power they are using. Nothing showing there.