It seems strange that you stated it works fine with one battery but not another. Is there any reason for using 12v, which will mean the regulator will need to drop 7v which would generate a fair amount of heat. I would make a simple supply for testing of 6v transformer, rectifier, and a couple of 2500uF electrolytic capacitors (or use one of those DC plug type power supplies, and do away with the rectifier ), Then use the 100 / 200 nf caps either side of the regulator. It's also worth mounting the regulator on a heatsink. This should give you a very stable, smooth 5V dc supply for testing.