I, contrary, think that you are actually missing something, and so are the other answers except CCarter's answer. (That's a pity one needs over 50 reputation to comment, as it would be more suitable I guess....)
What I consider a flaw of any discussion like Eythyphro's dilemma, is the constant change of problem level we are talking on and the lack of linguistic reflection. Let me explain: as we discuss what is good, we are on the field of ethics. Then, you are asking a meta-ethical question (about the source of good in general, its possible creation by God and the implies of that hypothesis), but use arguments and examples back from the lower level: the permission to murder anyone without any reason is certainly something that's not "good" in any ethical system and our ethical intuition treats that as a valid argument against the possibility of creation of ethical system treating it the other way.
Apparently, this can not be considered as an argument: the field of meta-ethics doesn't know anything about why couldn't we name murder good, because that's not in the field of meta-ethical problems. Also, we need to checkout why the example of murder bothers us so much: the cultural and linguistic connotations about that case make an unjustified murder something bad almost by definition. When we enter the field of meta-ethical discussion, we should double-check every definition we use and whether we are even allowed to talk about something.
The concept of bad God is indeed, as CCarter points out in the last paragraph, self-contradictory. I even consider a mistake making an assumption that "there is no God, but objective values do exist", and so I agree with the statement that "without God, everything is permittable". Naming anything objective and absolute without concept of God is, in my opinion, in fact just creating a new God (what's more: if we associate it with a person who knows everything, we are happy to meet a new totalitarian dictator). The fact, that God is often impersonated while values and other abstractions are not is just another example of our cultural background. Therefore, see that using this statement as an argument of God existence is absolutely wrong, as it just tries to prove that there is something that's absolute and objective, often just by our intuition that murder being bad is so obvious it should be objective.
Now, to answer your question is theist's explanation of what's good just unsatisfactory as the atheist's approach. In my opinion, it is not. If we believe that something is objective and not just name it by convention, we have a strong basis and need not to develop further. We are sure. It is just like Newton's laws: as long as you stick to them, you are absolutely sure what should happen, what is possible ("good") and what is not ("bad").
But, at some point someone came up with an idea, that Newton's laws are insufficient and developed something new.
The knowledge we have is never 100% right, because we can never be 100% sure: we are just working with a model of reality, not with reality itself. When we change model, we can achieve something new (like quantum physics etc), but if we change the model of ethics at will, in most cases something really bad can happen, and even if not (we should, again, not use just our intuition) we can not predict what exactly would happen, and ethics is too serious business to play with it. That's why being assured that what is good is good in reality and not just by convention is more satisfactory: it just makes everything simplier. It doesn't help in explaining goodness, because note that goodness, whether God created it or just showed it to people, is, in this approach, an axiom, just like God.
I'm surprised no one has mentioned Immanuel Kant yet! Because he surely understood the theoretical problem I described above: note that Kant postulated the existence of God exactly that way and that is (in my opinion) brilliant: he did not try to prove his existence, but postulated it: he assumed we need objective values, and therefore just showed that we need God to have them. (If I simplify too much or maybe do not understand something, feel free to correct me.) Kant also proved that there can not be any proof or disproof of God's existence.
I hope one day, people from both sides of the debate, theists and atheists, would finally understand that. Or just rename their discussions to something like "Do we need God?", which may be a little less pointless.