I’ve so far found that the problem lies in the template-functions, where previous_post_link resides. It looks like the code used to generate the address for that link obtains the blog address first, and then adds the requested link, which in this case breaks down.
On my site, I’ve just added some PHP to delete the extra characters, but that’s not a real solution, just a hack.
BTW, this has NOTHING to do with permalinks, by all accounts.