Out of the box PowerApps offers only a small palette of colors you can choose from. But since most companies have some design guidelines, specific colors may be required.
There is already a uservoice available for that topic: Link to user voice
For the time being here is a workaround.
1. Save the .msapp file to your computer (File – Save as)
2. add the ending .zip to the download file
3. open the package (do NOT extract) with e.g. WinRar
4. edit the file Publishinfo.json (in folder Resources) and change the color code
5. save a copy of the file to your local drive
6. now DRAG&DROP the modified file into the package
(do not extract and re-pack, it will not work)
7. remove the .zip ending from the package
8. in PowerApps EDIT the app you want to change
9. go to File – Open and upload the modified .msapp package
10. go to File – Save and click on “Raplace existing app here”
11. Publish the app
Boom! It’s done