Turns out there was an issue with my nameservers at my host. I figured this out using information here: http://www.magentocommerce.com/boards/viewthread/50611/ (the referenced thread can be viewed in the internet archive, here https://web.archive.org/web/20150315055800/http://www.magentocommerce.com/boards/viewthread/50611 )
After that I received an error message associated with a blocked IP. I added my new ip at accounts.authorize.net in Tools (top menu) > Fraud Suite (left menu) > Authorized AIM ip addresses (body, second to last item).