Apenas escape em $ em $1 :
rename "s:(.*)$(date +"%Y%m%d"):\$(date -d "+1day" +"%Y%m%d"):" *
Mas você pode simplificar seu padrão assim:
rename "s#$(date +%Y%m%d)#$(date -d +1day +%Y%m%d)#" *
(isto assume que # não aparece na expansão de date ).