Why don't black boxes have their own GPS?
First let's and define what "too many cases" means in terms of cold, hard, unfeeling numbers (as best we can):

Wikipedia has a list (admittedly incomplete) of crashes where the CVR/FDR was not recovered. There are 16 crashes listed. I'll further add Air France 447 (which took "a long time" to find), and MH370 (which is currently unrecovered), bringing the total to 18.  

As Wikipedia admits their list is incomplete I'll double-and-round that in the name of being pessimistically conservative and say that since 1965 there have been 50 cases where it has taken "a long time" to recover the flight recorders (or they were never recovered). 

In a single year there can be over 100 "incidents". Even if we assume the CVR/FDR data wouldn't be useful for all of them there are still many hundreds (if not thousands) of incidents since 1965 where the cockpit voice recorder and/or flight data recorders have been recovered along with other wreckage or damaged airframes - often within a matter of days or hours (as soon as investigators can get to the wreckage). That's a pretty good track record.

One could certainly argue (legitimately) that "one unrecovered flight recorder is too many", and indeed the goal is to always find the recorders and analyze their contents.
If we're being realistic about this though we're going to have to accept the fact that sometimes you're just not going to recover the recorders: Aircraft crashes are messy, high-energy affairs and often involve inhospitable recovery environments like "the bottom of the ocean".


  If someone has better statistics close at hand I would love to review them and update this answer. Otherwise, it should be obvious that the above is an extremely rough off-the-cuff estimate, and should not be taken for any research or investigative purposes.
  In case it's not obvious - well I just said it.




Now, to the meat of your question:

Theoretically you could include a locator beacon in the CVR or FDR - incorporating a 406MHz ELT into the black box design is possible (you could even add a GPS to encode the device's location, though it would be of limited additional value with the inherent location accuracy of the 406MHz locator signal and satellite search system).

So why don't we do it?

As Lnafziger pointed out, airliners are already required to carry emergency locator transmitters - in any case where such a beacon would function including one in the CVR/FDR would be redundant with existing equipment in the aircraft.

Further practical problems arise when you consider the kind of abuse a "black box" is subject to -- These things need to survive a crash (up to 3400 Gs), crush forces, fire, and immersion in water under pressure.
Your typical distress beacon requires an antenna and a view of the sky, both of which would be in serious doubt after a crash:  The black box may be inside or under wreckage, required external antennas may have been torn off or burned away, and distress beacon signals are unlikely to be received if the recorder is under water (this is why current generation recorders have sonar "pingers" to assist in locating them).


  To easily illustrate the sort of problem radio devices have with "stuff" between them and the sky, try this experiment: Take your cell phone, wrap it in aluminum foil to simulate the skin of a plane, put it in a zip-lock bag, and take it to the bottom of a pool. I bet you won't be able to get a call on that phone.




Given the numerous failure modes (all of which are fairly high-probability in a real-world crash scenario), and the fact that we usually have a pretty good idea of where an aircraft is when a crash does happen, there isn't much to be gained by including additional locator technology in the CVR/FDR designs at this time - it just adds more components that would need periodic testing and recertification to ensure they are functioning properly and would activate appropriately in the event of a crash, while not appreciably improving our odds of finding the recorders.