Never changed anything on the phone. Fixed the issue though. I was using an older version of ADB: 1.0.31
Older versions don't support key RSA authentication.
Past devices: HTC Dream (Rogers), Acer Liquid E, HTC EVO3D GSM, HTC Panache (international myTouch4G), Huawei Ideos U8150, Rogers HTC Magic (myTouch3G variant)
Current devices: Samsung Galaxy Nexus GSM (i9250), ASUS Transformer TF300, Samsung Galaxy S3 i747m (Telus), Huawei Ideos S7