The names for Android versions are all confectionary-themed and run in alphabetical order: Cupcake, Donut, Eclair, Froyo, Gingerbread, Honeycomb, Ice Cream Sandwich, Jellybean, KitKat and now Lollipop. I have the latter on my new cell phone and it's great. Especially compared to Donut which was on my first smartphone.
Back to the O.P.'s original issue. I think the best bet is a factory reset. According to this post
it's a bit of a pain but greatly improves speed.