From Madrid, I would head to Sevilla and spend 3 nights there, but on your way, stop in Cordoba for a day. That way you'll spend 2 days, 3 nights in Sevilla and you could easily do Cordoba in a full day. You can store your luggage at the Cordoba train station and explore.
Here's a Cordoba info link that lists the sizes of the lockers in the train station in case you were worried about fitting suitcases:
(go to tips, and FAQ)
http://www.infocordoba.com/spain/andalusia/cordoba/travel_tips_for_cordoba_spain.htm After that, you can take the train to Granada for 2 nights, or 3 if you'd like to spend more time there rather than Sevilla. However, the train trip to Barcelona from Granada is 12 hours- you can do an overnight train or fly if you don't want to suck up a whole day of your trip.
Approximate train prices would be:
Madrid to Cordoba: 55 Euro (fast AVE train, less than 2 hours, leave about twice every hour)
Cordoba to Sevilla: 14-22 Euro depending on the speed of the train, less than an hour trip
Sevilla to Granada: 20 Euro, 4 per day
Granada to Barcelona: 55 Euro, overnight train bed prices vary, but 12 hour trip...
Not too bad, all in all! I'm doing a similar trip when my family comes to visit me next spring when I study abroad, we're just doing everything backwards (starting in Barcelona) and spending another day in Granada because that's where I'll be studying. We're only doing 2 days and 1 night in Sevilla because of time constraints with my classes.
You probably already have it, but here's the link to the renfe site:
http://horarios.renfe.es/hir/ingles.html# Happy planning!