I use Marvis and it scrobbles. They have a free version with ads and the paid one is only $3.99. Lots of options for sorting and play order unlike the stock music app.
Also they 'fixed' the scrobbling from your desktop that broke with the last iTunes update. Too bad iTunes is still broken though.