Ok, here's another trick to add to the pile of good answers above.
This one's a bit more brute force, most of the time it helps, sometimes it doesn't, and while it's probably only a first step toward fixing the problem (rather than a solution unto itself, which it's often not), it can help get you to where you can open the shapefile. Most cases you'll still need to do more manual repair in ArcMap after the shapefile opens (corrupt features?, missing attributes? misaligned attributes? etc.)
Copy the shapefile into a new empty folder. Only take the SHP, SHX, and DBF with you. Leave all other files behind, and yes that includes the prj.
(Windows): right-click the SHX file and select "Properties" to open the file properties.
On the "General" tab take a look at the EXACT file size of this SHX file down to the byte. Look at the "Size" property, and not the "Size on disk" property.
Take that file size in bytes and subtract 100 bytes (the header). Of the remainder, divide by 8 (the size of each "word"). The result gives you the number of shape features inside the SHP part of the shapefile.
Open the DBF in some software that is going to allow you to edit the DBF and save it back out as a DBF. Add or remove records in order to make the rows in the DBF match the number of shape features in the SHP you calculated in step #4. (If you're using an older version of Excel, keep in mind that Row #1 contains the field names, so if you're going for 1,000 records, that'll end up being 1,001 rows in the sheet since the first data row is Row #2.) If in order to make the number of rows match you needed to delete rows and those rows had real data in them you need to keep, just save those out to a new DBF, and you can readd that stuff back in later, once you've gotten to the point where everything opens up again in ArcMap.
Once you've used the steps above to match the number of features in the SHP with the number of rows in the DBF, try to open the shapefile again in ArcMap.