Correspondence colorings of graphs were introduced in 2018 by Dvořák and Postle as a generalization of list colorings of graphs which generalizes ordinary graph coloring. Kim and Ozeki observed that correspondence colorings generalize various notions of signed-graph colorings which again generalizes ordinary graph colorings. In this note we state how correspondence colorings generalize Zaslavsky's notion of gain-graph colorings and then formulate a new coloring theory of permutation-gain graphs that sits between gain-graph coloring and correspondence colorings. Like Zaslavsky's gain-graph coloring, our new notion of coloring permutation-gain graphs has well defined chromatic polynomials and lifts to colorings of the regular covering graph of a permutation-gain graph.