Thanks to Tim Layton, an Android Developer willing to contribute to the beginner/learning community, there is now a detailed series of video tutorials on beginning Android application development. These videos won't teach you to be a "programmer", they are targeted more towards people with software development and Java experience. Consider these videos to be lessons about Android's unique application types and development environment.
Before following this video series, it is recommended that you check out the official Android Developers videos found here. As always, your best resources are going to be the official Android Developer's Guide and the Android API Package Index.
Tim's videos are numbered and it is recommended that you start with "Android - Lesson 0 - Getting Setup for Development", the entire youtube playlist is embedded here:
To see all of Tim's Android tutorials check out his website.
If you end up making an awesome Android app and publishing it to the market, let us know in the comments so we can check it out! Happy Development!