Just deleted and reinstalled. Same thing and I'm sure I gave it Super User privileges this time.
Ok, I'm assuming your using Windows and have the drivers for the phone installed.
Don't know if you've ever used ADB, but it'll let you log into your phone and execute commands. Download the attached zip and extract, there will be 3 files: adb.exe and two DLL's.
Make sure USB debugging is turned on on your phone. Check in Settings>Applications>Development. Check the box next to USB Debugging.
Open a command prompt, navigate to whatever directory the three adb files are in (for simplicity sake, just put them in the root of your C drive.
Type: adb shell
You should get a few messages about starting a dameon and then a #. You might also get a prompt on your phone asking to grant root permissions. If so, grant it.
Type: cd system/app
Type: rm Browser.apk
Type: rm Browser.odex
Barring any errors, that *should* get rid of these files. Check it with Root Explorer to verify that they're gone. Let me know if you run into trouble.
Also, start the task manager on your phone and make sure the browser isn't running. If it is, that could be why the files aren't getting deleted. If it is, kill it and try to delete them with Root Explorer first (it's just easier), and then this way if it doesn't work.