Where did the startup-applications-preferences program go?

The if you can't find the program anywhere, try running gnome-session-properties from the command line (or alt+f2).

If it's not installed, I'm sure you can install the package gnome-session-properties.

The name of the program you are looking of is "Startup Applications"

Simple type at the dash "Start" and it will show up.

For Unity users, please note, the startup doesn't always appear in the Dash search bar.

On Ubuntu 12.04, try on the other side, in the menu you use for logging out and shutting down (the one with the cog icon).

Otherwise, use the answer given above: type gnome-session-properties into a terminal or add a soft link to /usr/share/applications. (This works in 13.10)