Есть ли объяснение этому поведению?

Если вы используете tox для запуска тестов на нескольких версиях Python, вам может потребоваться установить библиотеки разработчиков Python для каждой версии Python, на которую вы тестируете.

sudo apt-get install python2.6-dev 
sudo apt-get install python2.7-dev 
etc.