The problem you have is caused by the default installed idle → desktop association.
Nautilus, at least on my 12.04 Ubuntu (Classic Desktop), doesn't seem to have anything with which you can associated (new) commands with a certain filetype (as some Desktops/Browsers) and the list doesn't show idle at all, even if installed via apt-get install idle:

You can get the screen by right clicking a .py file, selecting Properties then the Open With TAB, and then click Show other applications (going via the Open With menu gets you the same result).
You have to correct the .dekstop file for idle by editing
/usr/share/applications/idle-python2.7.desktop as root (you might have idle-python3.desktop, depending on what version of idle you installed).
[Desktop Entry]
Name=IDLE (using Python-2.7)
Comment=Integrated Development Environment for Python (using Python-2.7)
Exec=/usr/bin/idle-python2.7 -n %f
Icon=/usr/share/pixmaps/python2.7.xpm
Terminal=false
Type=Application
Categories=Application;Development;
StartupNotify=true
What is missing in the installed file is the %f at the end of the Exec= line. Add %f there and save. Then in nautilus, right click a .py file and navigate to the Properties and Open With TAB once more (you don't have to restart nautilus). Now scroll down and Idle (using Python-2.7) is a selectable option (either as recommended application) or else first click it in the show other application list:

You can use Set as default to always open .py files with idle.
idlemanually as described in Gabor's answer? You can also try using the full path (open a terminal and runtype idleto get it).find /usr/share/applications/ -name "*idle*"