The reconquest of Africa and Italy was very possible (considering they were both conquered, even by rather small forces), as was the consolidation of rule in said territories. However, several factors played into the failure of the latter, and almost of the former.
If one can trust Procopios, which I do, except in the Anecdota, then Justinian was quite the penny-pincher when it came to the army. Also, until recently, scholars have underestimated and/or ignored the multiple outbreaks of plague during Justinian's reign. Such an epidemic would greatly reduce revenue and recruits for the army.
Concerning the army proper, some exarchs (military governors) were rather greedy folks who liked to bleed the area dry rather than pacify the locals. Additionally, even though they were able to win important battles, the comparably small number of soldiers sent to Africa and Italy were inadequate to effectively and permanently govern such large areas.