If our statements cut on December 31 with the fee changes and the changes take effect February 1, is this sufficient for the 30 day notice? Or since customers wouldn't receive their statements until the first week of January do we need to have our effective date later than February 1?

Notice under Reg DD is considered given when sent. Receipt is not an issue. So base your 30-day period on the mailing date for those statements. For e-statement and hold statements, use the date the statement will be made available.