I would say the most important part to start with in a game (after you jot at least some basic ideas down on what you want it to be like), is the game mechanics or "engine".
Graphics styles can change all the time until you feel it suits the game, but sometimes it helps to also start drafting up some simple graphics and menus in M$ Paint or on paper to decide how you want it to be laid out.