Is there any reason the Search and Replace plugin couldn't be used to change the default WordPress table prefix (wp_)?
In other words, could you just search for "wp_" and have it replaced with "wp_xx_" in the entire database?
Is there anywhere "wp_" is used in the database that isn't a prefix - potentially breaking something if it's changed?