Is there a way to start a Minecraft server when a player tries to connect to it?

Some people have wrapped the bukkit server in such a way. Some games hosting services also provide this kind of functionality, called "performance mode" or "hibernate mode" :

It displays a message during startup (as you mention in your comment) and it goes into hibernation again after an idle time.

As mentioned depending of your config as the full startup sequence of a minecraft server can be quite lengthy users won't be able to connect to it during boot up time.

There are plugins and programs that let you put your server into a mode called sleep mode, when in this mode the server is shown in the list as online but is really offline. When a person tries to connect it will give them a message along the lines of; Server Starting and send them back to the list screen. The server will then automatically start up and boom your only running the server when people are on. With programs/plugins such as this it also lets you set how long after the server having no people on will it be before it shuts down. I am sorry I cannot provide the links to the programs/plugins but if I remember them I will post them here.

As Mushu said, you would need a wrapped Minecraft server. McMyAdmin can be easily configured to do such job. Go to Configuration -> Features tab -> Set 'Enable server sleeping' to Yes and configure the time below.

Try this link:

https://github.com/gekigek99/minecraft-server-hibernation

It's a program that I created which starts up the server when a player tries to join and shuts it down when no players are online.