I have been pulling my hair out over this all morning. I just went to try Sellhigh’s idea of cutting out that final %/ from my custom structure when I noticed a single space at the end of the permalink string, just after the final percent sign (I didn’t have the slash there anyway) I deleted that and hey presto! All working again. It now reads /%category%/%post_id%
Check for that space folks!
Tom