Unless you have a prepay penalty and want to avoid paying the prepay penalty, there is no minimum time you must wait in order to refinance. As soon as you are able to qualify for better terms, you may proceed down that road.
How long has your husband been working part-time for? Part-time usually needs a full 2 years in order to qualify. Also, did you recently change jobs or are you going back to work? If you've recently changed jobs, and as long as you came from a job in the industry and have been in the industry for 2 years, your employment should be fine to qualify. Even if it hasn't been a full 2 years exceptions are made quite often.
The second your paid off mortgage/HELOC reports to the bureaus (which could be 2 months, or 2 days after being paid off, up to your lender) your score will change... if the HELOC reported as "revolving" and was close to it's limit you should see a pretty hefty increase on the scores.
Free Mortgage Advice & Pre-Approvals (FHA, VA, USDA, Fannie, Freddie, Non-Prime, Construction, Renovation/Rehab, Commercial) since 2002
Located in Southern California and lending in all 50 states