Thanks for the responses everyone.
Yeah, I think over-optimization is to blame here, I hate it when that happens. A draw call for each album seems like the way to go
Thanks for the tip about sprites, I had forgotten about those. So it sound sounds like you're also saying to use a draw call per album, but using point sprites instead of quads?
PBO's sound interesting, but unfortunately they don't seem to be supported in GLES 2 that I'm targeting. I wish they were though, sounds like that would be the best way to update the textures