I'm thinking that John Tilley (jtilley) is probably the best source of information on this matter, since the painting of the "Federal" frigates was proably greatly influenced by the practices which were followed for the frigates built during the Revolution.
I found the illustration below off the U.S.S. Constitution off Tripoli in 1804 on the web some time ago while considering the same subject.
Assuming that this is accurate, the paint scheme seems to follow the general pattern for English warships for the period 1775 through 1798 (please see Model Ship Builder, Mar/Apr 1987, "English Warships in the Daysof Sail, Part IV"):
Hull: Yellow with black wales (in the picture above, the yellow extends far below the gun ports, so it is probably more than a streak) - the brig trailing the Constitution definitely has a yellow hull. It also looks as though the masts are yellow (rather than white)
Upper works: Black, yellow or gilded carved work
Interior: Red (more likely green, but this is a guess on my part).
Bottom: Copper
Chapelle, "The American Sailing Navy," notes that "...the painting of the ships of the Navy was left to the commander's taste for a very long period; at least no regulations concerning this have been found prior to the '30's [1830's]. In the War of 1812, the American frigates were usually black, with a bright yellow streak along the gun ports, British fashion." (page 417).
Good luck!
Mike