Should a graduate student instructor write a recommendation letter?
If the class is yours entirely (meaning you're not merely covering one day out of three weekly sessions for a faculty member), then I hope you do write the letter. You are the instructor of record, you are filling the role of faculty in this class and the role of professor for this student, and I cannot imagine someone being qualified to teach an upper-division seminar but not being qualified to compose a recommendation letter. 

If it helps you feel less impostor-like, you can disclose the nature of your assignment in the letter. "Student A was an exemplary student in my "Life as a Repeat Game" seminar--a course I taught as a teaching assistant during my final year of graduate study." I would stay concise, highlighting essentials and avoiding flowery praise, but your question doesn't ask for advice on writing a letter of rec. :-)