What is the optimal exploration-exploitation trade-off in Q*bert?
I can spot three, maybe four, things in your implementation that could be contributing to incomplete learning that you are observing.
More exploration in long term
I think you have correctly identified that exploration could be an issue. In off-policy learning (which Q-learning is an instance of), it is usual to set a minimum exploration rate. It is a hyperparameter that you need to manage. Set too high, the agent will never experience the best rewards as it will make too many mistakes. Set too low, the agent will not explore enough to find the correct alternative actions when the opportunity to learn them occurs.
I would suggest for you something like:
epsilon = max(min(1.0, 1000 / (frames + 1)), 0.01)

You can choose numbers other than 0.01, but I think that is a reasonable start for many Atari games. You could try higher, up to 0.1 in games which are more forgiving of mistakes.
Remove dropout
I am not sure why, but I always have problems with dropout in RL neural networks. Try removing the dropout layer.
More convolutional layers
Convolutional layers are very efficient generalisers for vision and grid-based problems. You won't really benefit much from having a single layer though. I would add another two, increase the number of output channels.
Maybe state representation?
It is not clear from your description whether you are using a single colour frame for the state representation, or stacked greyscale frames for the last 3 inputs. It should be the latter, and if you want to more closely replicate the orginal DQN Atari paper, you should take the previous 4 frames as input.
In addition, you should be normalising the input into range $[0,1]$ or $[-1,1]$. The native image range $[0,255]$ is tricky for neural networks to process, and quite common for value functions to get stuck if you don't normalise.