Does a letter of recommendation from a postdoc who's been my instructor carry much weight? In large universities, undergraduate students tend to receive instruction mostly from recent PhD graduates or post-doctoral fellows. This is especially true during the first two years, when students may also have PhD students as instructors for their classes. 

During the application review process, how much weight would you put for letters written from post-doctoral fellows? Is the job title something that people care a lot about?
The issue with getting a letter from a post-doc is not their job title; it's the degree of experience they have with different students, and the authority with which they can judge their preparedness for a graduate program.  So, it's not that a letter from a postdoc is unacceptable and as soon as they have an assistant professorship everything is great.  There's a subtle continuum where the more experience someone has, the more weight their letter has, because they have known so many more students.  

Also, this is a bit more cynical, but humans are social creatures.  It's well-nigh unavoidable that they give more weight to a letter from someone they know personally.  A postdoc is much less likely to be well-connected and thus able to leverage this for you.