I've recently changed my permalink structure to this custom one:
/%post_id%/%postname%

Though it's changed, whenever I click on a particular post to read it in full, and then click one of the header links (which are category links) it just adds the link onto the end of the URL in the address bar already, and doesn't actually follow onto the page as desired.

I hope this makes sense, if not here's the link to the site:
http://www.deadpress.co.uk

If anyone could help me with this as soon as possible, I'd really appreciate it.

I can't see any problem on your site. Did you resolve this?

Yeah, I managed to resolve it, cheers.