After I did the simple Hello world I wanted to learn more. I quickly realized I need to try to learn Java first. Being a C# developer it should not be hard to do, like any language it is the syntax you have to learn.
In walks MobileTuts+. They have a nice little starter that seems to give you some idea as to what is in ahead. At their site you will find a tutorial called Learn Java for Android Development: Introduction to Java.
I have only had time to get as far as the first challenge. As some one who knows nothing of Java I feel this is a good start.