I see no reason why that circuit shouldn't work.
I can only suggest going back and double checking your connections. I have attached a schematic to help.
Note that the + terminal of the supply goes to the Input pin of the 7805, and the - terminal goes to the GND pin.
