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
).