yeah, you got shitty steaks.
Toughness has nothing to do with how cooked it is, except under crazy circumstances like you slowly baking all the moisture out of the meat. Even then it would just get crumbly, not tough. I'm not sure where you got this notion that overcooked = tough.
You understand that tough meat is meat with a lot of fibrous/sinewy muscle tissue running through it, right? You can't add this tissue if it isn't there in the first place.
There are a few things you can do to soften it up though if you have shitty beef. You can make it tender by cooking it in a broth (stewing) or slow cooking it in liquid (crockpot) for a day, or by tenderizing it with a *gasp* tenderizer.
Also: failing to cook beef on a propane grill is pretty sad.