Premature optimization and design paralysis are evil. Don't fall into the trap of worrying about a simple check. If you're concerned, implement and profile.
I think you're under-estimating how powerful hardware can be - even the low-end hardware. An if statement comparing a simple boolean is pretty cheap and should be the least of your concerns in a game. I agree that checking for the condition every frame isn't ideal - but there a lot of difference ways you can circumvent this if you're that concerned. The check is extremely cheap and many others have went over this - but I'll try to give yet another detailed explanation. You've tagged this under Java and C++ and mentioned Android 1.5 in a comment - so presumably that is your target.
Check only when necessary. If you have an objective that is obtain a score of 10, 000 points; add a check on your setter for score or add a callback to the achievement manager, preferably to verify this. The objective manager would just be a simple hash map of enums and booleans; (I picked hash map for the fast lookup times) the callback makes a quick lookup into this table and sets it to unlocked if needed.
Optimize for the game objectives. If your game objective is "kill 5 ships", keep a counter of the alive ships left; don't query the game state directly. Evaluate the state deltas as they are completed so you don't have to do an expensive computation all at once. This is handy if your objective requires a lot of spatial probing that might be expensive. Does every yellow box need to be touching a green box? On collision, set a flag to determine this and then unset it when the object moves off. Keep the state easy to access and query.
Defer the check. If your check is more expensive than a single lookup and a few comparisons (expensive property getters, functions or lots of checks) and you really think you can't optimize the checks, then you can always defer your check. Your game likely has states that are idle or the player is not doing a whole lot. It's tough to say without knowing your game - but let me give a general gist.
We'll use Angry Birds as a quick example here to illustrate the purpose. Angry Birds probably has a lot of states in its state machine - but for simplification reasons we're going to assume just two.
The first state is when the birds are resting on the slingshot; they're idle and not doing anything and just waiting for user input. Not a lot of stuff is going and small FPS drops would go unnoticed the minute this state is transitioned to.
The second state is of course when the bird is flying through the air. After this state finishes (the bird has finished flight), the game transits back to the slingshot (state 1) and checks to see if all the pigs have seen defeat.
The idea of deferring the objective checks works exactly like Angry Birds does - you can queue up plausible objective checks that could have happened during that state and then you verify later when the load is acceptable and the end user won't notice any obvious frame drops.