|I||Independent||The user story should be self-contained, in a way that there is no inherent dependency on another user story.|
|N||Negotiable||User stories, up until they are part of an iteration, can always be changed and rewritten.|
|V||Valuable||A user story must deliver value to the end user.|
|E||Estimable||You must always be able to estimate the size of a user story.|
|S||Sized appropriately or Small||User stories should not be so big as to become impossible to plan/task/prioritize with a certain level of certainty.|
|T||Testable||The user story or its related description must provide the necessary information to make test development possible.|
One of the characteristics of Agile Methodologies such as Scrum or XP is the ability to move stories around, taking into account their relative priority - for example - without much effort. If you find user stories that are tightly dependent, a good idea might be to combine them into a single user story.
The only thing that is fixed and set in stone in an agile project is an iteration backlog (and, even then, it can be broken). While the story lies in the product backlog, it can be rewritten or even discarded, depending on business, market, technical or any other type of requirement by team members.
The focus here is to bring actual project-related value to the end-user. Coming up with technical stories that are really fun to code but bring no value to the end-user beats one of the Agile Principles, which is to continuously deliver valuable software.
If a user story size cannot be estimated, it will never be planned, tasked, and, thus, become part of an iteration. So there's actually no point in keeping this kind of user story in the Product Backlog at all. Most of the time, estimation cannot be executed due to the lack of supporting information either in the story description itself or directly from the Product Owner.
Sized appropriately or Small
Try to keep your user story sizes to typically a few person-days and at most a few person-weeks. Anything beyond that range should be considered too large to be estimated with a good level of certainty or even "epic" and broken down into smaller user stories. There's no problem in starting with epic stories, as long as they are broken down when the time to place them in an iteration backlog becomes closer.
Bear in mind that a story should only be considered DONE, among other things, if it was tested successfully. If one cannot test a story due to lack of information (see "Estimable" above), the story should not be considered a good candidate to be part of an iteration Backlog. This is especially true for teams employing TDD - Test Driven Development