The original author created a bug on php.net (https://bugs.php.net/bug.php?id=66444), where the correct answer was eventually posted. You need to use the undocumented method:
->setInterlaceScheme(Gmagick::INTERLACE_LINE)
Instead of:
->setImageInterlaceScheme(Gmagick::INTERLACE_LINE)
This worked for me! For reference I am using PHP 5.4.20 with gmagick 1.1.7RC2 on top of GraphicsMagick 1.3.18.