More information is needed. An experienced immigration attorney needs to read the decision to deny. If the change of status was denied, then it is possible that a finding of unlawful presence was made. This may complicate matters.
I strongly recommend an appointment with a candid and experienced immigration attorney, who can discuss your options and the potential consequences of consular processing. It is unclear without a thorough review to determine what is the best strategy at this point.
The above is general information and does not create an attorney client relationship.