CDbException: The DB query must contain the "from" portion
Traced the error back to the from function in Yii's craft/app/framework/db/CDbCommand.php:

$tables=preg_split('/\s*,\s*/u',trim($tables),-1,PREG_SPLIT_NO_EMPTY);


The preg_split documentation states "if matching fails, an array with a single element containing the input string will be returned" but I was just getting an empty array.

This made me suspicious of what the PREG_SPLIT_NO_EMPTY flag was hiding, sure enough without it I got an array with one empty string in it, as if there was a match.

Some trial and error later and adding the PCRE_UTF8 modifier u to the preg_split patterns seemed to solve the problem.

Unfortunately can't explain what's causing the encoding issues yet.