If permalinks does not automatically work on your WordPress multi-site installation you may have to include index.php before the custom permalink structure within the permalinks settings option panel:
/index.php/%postname%/
If this doesn't work, review your .htaccess file or open a support ticket.