Template Issue Regarding Permalinks

This is a first for me, I just uploaded my new template and everything was working fine, up until I looked at my category pages. I have my permalinks setup as http://www.domain.com/category/cat-name. And for whatever reason my images aren’t showing up. I looked deeper and noticed that the images aren’t being pulled from the right place. In the index and single post pages it pulls from http://www.domain.com/images/image.gif, whereas in the category pages it pulls it from http://www.domain.com/category/images/image.gif.

I had suspected that it may have something to do with the permalinks so I switched off from my normal custom permalink structure which is /%postname, to the default one with the numbers, lo and behold it works fine. I never had a problem with this before, so I have no idea what could be causing this, any suggestions would be greatly appreciated.