Finally the project reached the beta stage. We have implemented a simple terminal application that communicates an android phone with an arduino board using the audio channel. The current implementation allows sending and receiving integers (between 1 and 31).
The source code and the developer documentation is available at the Google code Androino project http://code.google.com/p/androino/
The wiki page contains the instructions to run the app and the source code (both android and arduino) is available for download here.