fieldsets (<legend> falls under that category) and labels should definately be used, I love it when I can use them. It's a shame that labels and fieldsets are not used more often because they make forms dramatically easier to fill out. Fieldsets should be used to seperate series of options. For example: You have a section for gender, the gender options (male, female) should be set inside of a fieldset using <legend> to put the word 'Gender' at the top of the box. This makes it easier for people to fill out large forms, especially users which are using an aural browsers because it helps orient them.
Labels should be used for checkboxes and radio buttons. This allows a much wider margin of error when checking to select an option (try clicking several of those boxes using a jittery wireless mouse *points at his parents*). A good explanation of this, is the way software installers work. They have the checkbox with a label titled 'I agree to these terms and conditions', you can click on the label text to select/unselect the checkbox.
Hope this helps
Sorry it's been taking so long for my web site update and forming the affiliation. I was REALLLLLLY close to updating the live site when BAM, lightning struck and I had to format my HD to get my comp working again, I had no method of backing up the whole last MONTH'S work *sighs*. I'm probably going to throw an affiliates section on the current website without any other updates just so I can get you off of the 'waiting list' (although, no list exists) lol. Sorry about my unreliability on this issue.