I've had some issues with Drive Time that were related to the Tele Atlas data. It is possible that the data is not allowing Network Analyst to create the Service Area if a store point is located near a street segment that has a routing restriction. In these cases, problems with one of your drive time calculations would cause the whole process to fail. Unfortunately, in this case, there is probably no way to know which store is causing the problem, so your best bet is to batch the process with smaller groups of stores so that you can determine which area has the problem. After the batch process completes you can merge all of the trade areas into a single map layer.
It could also be a memory issue if you have very large drive time minutes for your settings. Again, doing a smaller subset of the stores in a batch process would be the way to go.
Regards,
-Susan-