A typical case of overblown 'user failure', not Android security model failure. If a wallpaper app wants internet access and you allow it you really only have yourself to blame. Wallpaper, cursors packages, screen savers and other dumb 'customisation' gadgets have been malware vectors on the windows platform for about 15 years now, why would phone platforms be any different ?
Because this wasn't some random APK downloaded directly from the internet and thrown onto a phone after the 'APKs from the internet might harm your security' message. It was uploaded to Android Market and provided by Google, who as an arbiter of content, should realize that 'collect phone data' isn't an appropriate permission for a wallpaper.
I really think that goes one step too far, that's exactly what apple does with their market place and I think that is a big part of the problem.
The ultimate responsibility of what you run on your computers lies with you, not with some entity providing you with a convenient way to get at a catalogue of stuff.
This application seems to be malicious, and it seems that the security model is not broken, after all it asks for the permissions very explicitly.
Now if only people would read those warnings and think for a bit before clicking 'ok'.
This is analogous to people receiving an email that instructs them to open a malware attachment.
It's simple, if you haven't inspected the source and it doesn't come from a source that has inspected the code and that gives you a guarantee that you can trust the stuff you download then you can not trust it.
Pushing the responsibility to Google is utterly unfair, they could never in a lifetime review the source code of every application that every android app developer throws out there.