That will be my last resort. If I do re-install it, would I lose any of my album artwork or no?
You won't lose anything (artwork, playlists, play counts, etc) uninstalling and reinstalling. Your iTunes library won't be removed.
How large is your iTunes library? I have heard of some people running into problems with libraries exceeding 20gb. I suspect that there may be some kind of fragmentation issue.
I doubt that's the problem. My library is 130GB and I don't have any problems.