Yes, ulice is feminine. Just because a noun has a -e doesn't make it neuter.
The "template" words (sorry, I don't know the proper term for these) for feminine are: žena růže píseň kost
It turns out that an -e noun can be any of the genders! It can be masculine (following the "soudce" template), feminine (following the "růže" format), or neuter (following either "moře" or "kuře").
Edit: It turns out that the "templates" are supposedly called inflectional paradigms.