Actually my memory was jogged. This is entirely caused by AMazon Linux having massively oudated versions of pip and virtualenv installed.
Updating pip/virtualenv solved it:
pip install --upgrade pip
pip install --upgrade virtualenv
I came across a similar issue with other packages.