How can I use a cross compiler with Scons?

Following the advice on the Scons FAQ and from an old mailing list thread, I've built up a really simple SConstruct and SConscript that I thought would build an example app, but errors out with:

scons: Reading SConscript files ...
scons: done reading SConscript files.
scons: Building targets ...
nios2-linux-gnu-g++ -o src/bin/example/example.o -c src/bin/example/example.cpp
sh: nios2-linux-gnu-g++: command not found
scons: *** [src/bin/example/example.o] Error 127
scons: building terminated because of errors.

Ugh. My SConstruct file:

import os

env_options = {
    "CC"    : "nios2-linux-gnu-gcc",
    "CXX"   : "nios2-linux-gnu-g++",
    "LD"    : "nios2-linux-gnu-g++",
    "AR"    : "nios2-linux-gnu-ar",
    "STRIP" : "nios2-linux-gnu-strip",
    "PATH"  : os.environ['PATH']
}

env = Environment(**env_options)
Export('env')

env.SConscript("src/bin/example/SConscript")

and the SConscript it calls:

Import('env')

env.Program("example", ["example.cpp"])

Here's what I think are the relevant parts of env.Dump() (If something's missing let me know):

{ 'AR': 'nios2-linux-gnu-ar',
  'CC': 'nios2-linux-gnu-gcc',
  'CCCOM': '$CC -o $TARGET -c $CFLAGS $CCFLAGS $_CCCOMCOM $SOURCES',
  'CCFLAGS': [],
  'CCVERSION': '4.8.2',
  'CFILESUFFIX': '.c',
  'CFLAGS': [],
  'CPPDEFPREFIX': '-D',
  'CPPDEFSUFFIX': '',
  'CPPSUFFIXES': [ '.c',
                   '.C',
                   '.cxx',
                   '.cpp',
                   '.c++',
                   '.cc',
                   '.h',
                   '.H',
                   '.hxx',
                   '.hpp',
                   '.hh',
                   '.F',
                   '.fpp',
                   '.FPP',
                   '.m',
                   '.mm',
                   '.S',
                   '.spp',
                   '.SPP',
                   '.sx'],
  'CXX': 'nios2-linux-gnu-g++',
  'CXXCOM': '$CXX -o $TARGET -c $CXXFLAGS $CCFLAGS $_CCCOMCOM $SOURCES',
  'CXXFILESUFFIX': '.cc',
  'CXXFLAGS': [],
  'CXXVERSION': '4.8.2',
  'HOST_ARCH': None,
  'HOST_OS': None,
  'PATH': '/home/chockey/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/home/chockey/bin/altera/13.1/quartus/bin:/home/chockey/bin/altera/13.1/quartus/sopc_builder/bin:/home/chockey/bin/altera/13.1/nios2eds/bin:/home/chockey/bin/altera/13.1/nios2eds/sdk2/bin:/home/chockey/bin/altera/13.1/nios2eds/bin/gnu/H-i686-pc-linux-gnu/bin',
  'TOOLS': [ 'default',
             'gnulink',
             'gcc',
             'g++',
             'gfortran',
             'gas',
             'ar',
             'filesystem',
             'm4',
             'lex',
             'yacc',
             'rpcgen',
             'jar',
             'javac',
             'javah',
             'rmic',
             'dvipdf',
             'gs',
             'tar',
             'zip'],

The tools most certainly exist at the first path entry (as symlinks, if that matters, but I tried adding the full path to the toolchain, that didn't seem to change anything):

/home/chockey/bin/nios2-linux-gnu-addr2line@   /home/chockey/bin/nios2-linux-gnu-gcov@
/home/chockey/bin/nios2-linux-gnu-ar@          /home/chockey/bin/nios2-linux-gnu-gdb@
/home/chockey/bin/nios2-linux-gnu-as@          /home/chockey/bin/nios2-linux-gnu-gprof@
/home/chockey/bin/nios2-linux-gnu-c++@         /home/chockey/bin/nios2-linux-gnu-ld@
/home/chockey/bin/nios2-linux-gnu-c++filt@     /home/chockey/bin/nios2-linux-gnu-nm@
/home/chockey/bin/nios2-linux-gnu-cpp@         /home/chockey/bin/nios2-linux-gnu-objcopy@
/home/chockey/bin/nios2-linux-gnu-elfedit@     /home/chockey/bin/nios2-linux-gnu-objdump@
/home/chockey/bin/nios2-linux-gnu-g++@         /home/chockey/bin/nios2-linux-gnu-ranlib@
/home/chockey/bin/nios2-linux-gnu-gcc@         /home/chockey/bin/nios2-linux-gnu-readelf@
/home/chockey/bin/nios2-linux-gnu-gcc-4.7.3@   /home/chockey/bin/nios2-linux-gnu-size@
/home/chockey/bin/nios2-linux-gnu-gcc-ar@      /home/chockey/bin/nios2-linux-gnu-sprite@
/home/chockey/bin/nios2-linux-gnu-gcc-nm@      /home/chockey/bin/nios2-linux-gnu-strings@
/home/chockey/bin/nios2-linux-gnu-gcc-ranlib@  /home/chockey/bin/nios2-linux-gnu-strip@

How do I get scons to find my toolchain?

You're almost there. You're adding your PATH to the SCons construction environment instead of to the ENV key of the construction environment:

import os

env_options = {
    "CC"    : "nios2-linux-gnu-gcc",
    "CXX"   : "nios2-linux-gnu-g++",
    "LD"    : "nios2-linux-gnu-g++",
    "AR"    : "nios2-linux-gnu-ar",
    "STRIP" : "nios2-linux-gnu-strip",
}

env = Environment(**env_options)
env.Append(ENV = {'PATH' : os.environ['PATH']})
Export('env')