We've had one other report (in the Lollipop thread) of a developer needing to drop their texture sizes in order to run under Android 5. Can you tell me how large your textures are, how many of them you have, and whether or not you generate mipmaps with them? We don't know of any general loss of texture memory under Android 5, but it's certainly possible that the OS needs more than it did before.
I thought we may have been pushing the texture memory a bit on 4.4.4, but we had no issues so we never gave it much thought.
Currently our largest texture is 2048x2048 (we have about 5 in total but no more than than 2 or 3 get used at the same time) and the vast majority (around 50+) are no bigger than 1024x1024. All textures currently have mipmaps enabled on them