I kept toying around with this problem. My laptop has winxp. It would beep when I put the cable in, but I was always disappointed by no connection. Then my phone would tell me to try and download Kies. Did not want to do that. But I did. Connection could still not be made.
I stumbled onto a fix. Dunno if it will work for anyone else. I was juggling about 2 dozen things at the time and might have missed a critical step.
I plugged in a USB OTG cable with an 8gb flash drive. The phone recognized it! Even displayed a cute little message in the status bar that USB was connected (instead of MTP). This all lasted a whole 2.7 seconds after hours of searching for solutions.
I tried connecting it to my computer for another try, and I am proud to report that is is working flawlessly for now!!