Pode ser o redshift que não consegue descobrir sua localização, pois acredito que ele usa o relógio do Gnome para fazer isso.
Tente acessar o link e digite sua cidade. Em seguida, use a latitude / longitude mostrada em um comando do terminal da seguinte forma:
redshift -l x:y
x = latitude (ex. 56.15)
y = longitude (ex. 10.12)
ex:
redshift -l 56.16:10.12