Technically, the Android Open Accessory SDK requires either the Nexus S or Nexus One running Android 2.3.4. However, thanks to the latest CyanogenMod and some documentation from Mitch Altman, you can use it with other phones. Mitch has gotten it working with the G2:

On June 5th, 2011, about 40 people (or more) gathered at Noisebridge to put our collective heads together to get our Android phones going with Arduino.

I have a new (8 day old) T-Mobile G2 phone (also known as HTC Vision).
It came with a version of Android OS (v2.2) that does not support Arduino hardware (need 2.3.4 or later). So, with the help of Rubin and others, I rooted my phone, and installed the latest version of Cyanogenmod (a fork of the official Android OS).

I attempted to document the steps I went through, so that others can have an easier time of it.

The steps will probably be similar if you have another type of Android phone.

Notes from Android Arduino Meetup