Here are some user issues by Sonata owners with starting problems that I found last night that I passed along to my sister who owns the 2003 Sonata.
(As commenter 'oscargamer' wrote, "It could be many things." But the list below gives an owner some idea of things to consider.)
Among them are:
1. It sounds like the contacts at the end of the ignition are not closing. They could be dirty. They could be worn. They usually send a signal to a relay. That relay may be bad or have a bad connection.
2. The light does not turn on to indicate it is in park and until I jiggle the shift until the light does come on it will not start.
3. When leaving the restaurant, my car wouldn't start, not even turn over but I did have lights on the dash. Car was in park but we moved it in and out of gear several times while trying to start ( my husband said it had been acting up for about a week and shifting and going back to park allowed it to start.)
4. I believe it has something to do with the shifter contacting the Parked position sensor.
5. That problem seems to trace to a bad or misaligned sensor on the brake. It would need to be pressed all the way down to start. Using the same idea on my 2006 thinking the brake petal could be related, I would hold down the brake petal. It has started every time in the last day.
6. My car would sometimes start in Neutral when it wouldn't start in Park.
7. Ultimately, this turned out to be my starter. It finally wouldn't start one day when I was 1.5 miles from the dealer. I had it towed and they were able to take care of it for me right there and then (at about a $400 price tag).
8. After two days of intermittent issues I dropped the car at a different dealership and they diagnosed the starter (armature) as a failure in a half-hour. Covered it under warranty, and was told it was between $500-$700 usually. Technicians there told me its one of the most common jobs they do.