Yes, the EX:Sandstorm rulebook says that if you have only a fossil in your opening hand, you have the *choice* whether or not to shuffle your hand back into your deck.
Please note that this was not reprinted in the EX: Dragon rulebook (because there are no fossils in Dragon), but the rule still applies.
Hope this helps,
- CHRISBO