Turns out my test accounts were setup correctly in my sandbox. Problem was- I was using a CVV code of 123 when making test transactions, and a 123 CVV code is reserved for failure testing and cannot be used.
Instead I used another random code 456 and it worked fine.
Maybe this will help someone else working in sandbox mode.
Sandbox User Guide: