Personal Interests
Most game designers come up with ideas from things that interest them or that they are passionate about. For example, I really like Pirate based storylines, so it would be a lot of fun to create a game based around a Pirate theme.
Surrounding Elements
A lot of game designers will create games influenced by their surroundings. The connection to their surroundings might not be a replication or a direct connection, but their surroundings are able to influence their design. Let's look at the iconic Monopoly game. The creator of this game created it during the great depression as a "fantasy" style game to explore what it would feel like to gain wealth through property ownership.
Market Gaps
Professional game designers have the burden of not only needing to create new game ideas, but create game ideas that will be successful. During this process, game designers will often analyze the current state of the market and explore genres and themes that don't have a lot of compelling games within them.
Open up the app store on a mobile device. Look at the numerous genres and themes of games that are present. Start writing down the high level genres themes that you come across. As you come across duplicates, keep a running count or tally of how many games in a particular genre you find. After a while, look at your list and explore what genres or themes may be missing or have low representation counts. This might present an opportunity to create a game using a genre or theme that doesn't have a lot of competition.
Jobs / Careers
Basing a game around the many different jobs and careers that are present is another great way to come up with a new game idea. Kids in elementary school often dream about being an astronaut, a pilot, a fire fighter, etc. Creating a game that revolves around these storylines often have an easier time finding success simply because there is already interest from the user in the designated topic.
Frustrations
Yes - this is a legitimate way to come up with game ideas. Often game designers come up with great ideas because they get frustrated with how some other existing game works or doesn't work. Inventors and Entrepreneurs often work the same way. They come up with ideas to solve a problem or a frustration that they encounter.
Start Designing the Game
Using the areas above, think of something that you might want to create a game around. It doesn't have to be perfect right now. Instead focus on just the high level idea.
