Jel, need some additional information. Such as:
Total of all other monthly debt (minimum payments as reported on credit report)
Monthly gross income for you and wife/husband
When was your current mortgage taken out? Did you check with Fannie Mae and Freddie Mac to see if either owns your loan? If not, do that now.
Fannie Mae: http://www.fanniemae.com/loanlookup
Freddie Mac: freddiemac.com/mymortgage/ (add http:// before it)
If your current loan was taken out prior to May 31, 2009, and Fannie Mae or Freddie Mac own your loan, then you should qualify for a HARP refinance. (keep in mind there are some situations where you may not qualify).
Now, if neither or the two own your loan (or if the current mortgage was taken out after May 31, 2009), then you would be looking at a normal Conventional/Conforming refinance. In order to qualify the lender has to run your file through either Fannie Mae or Freddie Mac's automated underwriting system (AUS) and get an approval.
One thing that will cause you to not get an approval is debt to income ratios. On a 15 year fixed your debt ratios will be considerably higher than on a 30 year. That may be the reason that they couldn't get it approved on a 15 year, and also why I asked for your income and debt information.
If you don't mind me asking, what bank/lender/broker were you working with?