I have the same error when building 3.6.4, however not exactly with the same options. Some context first:
$ lsb_release -d; lscpu |head -1
Description:        Ubuntu 14.04.5 LTS
Architecture:          x86_64
$ gcc --version
gcc (Ubuntu 4.8.4-2ubuntu1~14.04.4) 4.8.4

I'm careful to start from a freshly untarred source tree. 

This configuration builds a working installation:
$ ./configure --prefix=$PYTHON --enable-optimizations --enable-shared LDFLAGS="-Wl,-rpath=$PYTHON/lib -Wl,-Bsymbolic-functions -Wl,-z,relro" --with-computed-gotos --with-system-ffi --with-fpectl --with-system-libmpdec
$ make profile-opt

However, I get the reported error when CFLAGS="-mtune=core-avx2  -march=core-avx2" is added. 

This set of options works fine without --enable-shared, i.e. this is what I am using for static builds:
$ ./configure --prefix=$PYTHON --enable-optimizations LDFLAGS="-Wl,-z,relro" --with-computed-gotos --with-system-ffi --with-fpectl --with-system-libmpdec CFLAGS="-mtune=core-avx2 -march=core-avx2 -Wformat -Werror=format-security"

Note, with the following configuration (-mtune without -march), compilation just blocks on Objects/memoryobject.c (ie, gcc never completes):
$ ./configure --prefix=$PYTHON --enable-optimizations --enable-shared LDFLAGS="-Wl,-rpath=$PYTHON/lib -Wl,-Bsymbolic-functions -Wl,-z,relro" --with-computed-gotos --with-system-ffi --with-fpectl --with-system-libmpdec CFLAGS="-mtune=core-avx2  -Werror=format-security"
$ make profile-opt