FWIW, I'm using a Freescale cross-compile tool-chain on a Linux x86-64 build host, although I have duplicated the cross-compile error on an x86 Ubunutu 10.04 build host.

Steps to reproduce:

$ wget http://www.python.org/ftp/python/2.7.5/Python-2.7.5.tar.bz2
$ tar -jxf Python-2.7.5.tar.bz2
$ cd Python-2.7.5
$ export PATH="/opt/freescale/usr/local/gcc-4.3.74-eglibc-2.8.74-dp-2/powerpc-none-linux-gnuspe/bin:${PATH}"
# For info only:
$ ls -l /opt/freescale/usr/local/gcc-4.3.74-eglibc-2.8.74-dp-2/powerpc-none-linux-gnuspe/bin 
total 10472
-rwxrwxrwx 1 root root  590485 Mar  5  2012 powerpc-none-linux-gnuspe-addr2line
-rwxrwxrwx 1 root root  614647 Mar  5  2012 powerpc-none-linux-gnuspe-ar
-rwxrwxrwx 1 root root  897161 Mar  5  2012 powerpc-none-linux-gnuspe-as
-rwxrwxrwx 1 root root  235382 Mar  5  2012 powerpc-none-linux-gnuspe-c++
-rwxrwxrwx 1 root root  589227 Mar  5  2012 powerpc-none-linux-gnuspe-c++filt
-rwxrwxrwx 1 root root  234277 Mar  5  2012 powerpc-none-linux-gnuspe-cpp
-rwxrwxrwx 1 root root    8503 Mar  5  2012 powerpc-none-linux-gnuspe-embedspu
-rwxrwxrwx 1 root root  235382 Mar  5  2012 powerpc-none-linux-gnuspe-g++
-rwxrwxrwx 1 root root  233126 Mar  5  2012 powerpc-none-linux-gnuspe-gcc
-rwxrwxrwx 1 root root  233126 Mar  5  2012 powerpc-none-linux-gnuspe-gcc-4.3.2
-rwxrwxrwx 1 root root   16512 Mar  5  2012 powerpc-none-linux-gnuspe-gccbug
-rwxrwxrwx 1 root root   28017 Mar  5  2012 powerpc-none-linux-gnuspe-gcov
-rwxrwxrwx 1 root root  655127 Mar  5  2012 powerpc-none-linux-gnuspe-gprof
-rwxrwxrwx 1 root root 1036372 Mar  5  2012 powerpc-none-linux-gnuspe-ld
-rwxrwxrwx 1 root root  603678 Mar  5  2012 powerpc-none-linux-gnuspe-nm
-rwxrwxrwx 1 root root  750617 Mar  5  2012 powerpc-none-linux-gnuspe-objcopy
-rwxrwxrwx 1 root root  895336 Mar  5  2012 powerpc-none-linux-gnuspe-objdump
-rwxrwxrwx 1 root root  614647 Mar  5  2012 powerpc-none-linux-gnuspe-ranlib
-rwxrwxrwx 1 root root  264063 Mar  5  2012 powerpc-none-linux-gnuspe-readelf
-rwxrwxrwx 1 root root  593901 Mar  5  2012 powerpc-none-linux-gnuspe-size
-rwxrwxrwx 1 root root  591853 Mar  5  2012 powerpc-none-linux-gnuspe-strings
-rwxrwxrwx 1 root root  750617 Mar  5  2012 powerpc-none-linux-gnuspe-strip
$ ./configure --host=powerpc-none-linux-gnuspe \
    --build=i586-linux-gnu --prefix=/          \
    --disable-ipv6 ac_cv_file__dev_ptmx=no     \
    ac_cv_file__dev_ptc=no
$ make

Make fails because the foreign (powerpc, in this case) pgen binary is used to build the $(GRAMMAR_H).  Instead, a native version of the python interpreter (preferrable) and pgen (essential) need to be built first using the host's toolchain.  Then, these tools can be used to build the full foreign suite.

FWIW, This 2 step process is well documented here:

http://randomsplat.com/id5-cross-compiling-python-for-embedded-linux.html

However, the cross-compile fixes from Issue17086 may have helped this process.  (It's hard for me to determine how to take advantage of these updates.)  Certainly, they changed the above process dramatically.

Incidentally, Python 3.3.2 exhibits almost the exact same build error, if not the same.

Build log on an x86-64 host for Python-2.7.5 for a PowerPC-linux target is attached.

Tail of log:

make Parser/pgen
make[1]: Entering directory `/home/user/Python-2.7.5'
powerpc-none-linux-gnuspe-gcc -c -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include   -DPy_BUILD_CORE -o Python/mysnprintf.o Python/mysnprintf.c
powerpc-none-linux-gnuspe-gcc -c -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include   -DPy_BUILD_CORE -o Python/pyctype.o Python/pyctype.c
powerpc-none-linux-gnuspe-gcc -c -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include   -DPy_BUILD_CORE -o Parser/tokenizer_pgen.o Parser/tokenizer_pgen.c
powerpc-none-linux-gnuspe-gcc -c -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include   -DPy_BUILD_CORE -o Parser/printgrammar.o Parser/printgrammar.c
powerpc-none-linux-gnuspe-gcc -c -fno-strict-aliasing -g -O2 -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include   -DPy_BUILD_CORE -o Parser/pgenmain.o Parser/pgenmain.c
powerpc-none-linux-gnuspe-gcc -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes  Parser/acceler.o Parser/grammar1.o Parser/listnode.o Parser/node.o Parser/parser.o Parser/parsetok.o Parser/bitset.o Parser/metagrammar.o Parser/firstsets.o Parser/grammar.o Parser/pgen.o Objects/obmalloc.o Python/mysnprintf.o Python/pyctype.o Parser/tokenizer_pgen.o Parser/printgrammar.o Parser/pgenmain.o -lpthread -ldl  -lpthread -lutil -o Parser/pgen
make[1]: Leaving directory `/home/user/Python-2.7.5'
Parser/pgen ./Grammar/Grammar Include/graminit.h Python/graminit.c
Parser/pgen: Parser/pgen: cannot execute binary file
make: *** [Include/graminit.h] Error 126
make Parser/pgen
make[1]: Entering directory `/home/user/Python-2.7.5'
make[1]: `Parser/pgen' is up to date.
make[1]: Leaving directory `/home/user/Python-2.7.5'
Parser/pgen ./Grammar/Grammar Include/graminit.h Python/graminit.c
Parser/pgen: Parser/pgen: cannot execute binary file
make: *** [Include/graminit.h] Error 126