This also happens if the paths are correct, but the service account is not the owner of the data files (yet it still has enough rights for read/write access). This can occur if the permissions for the files were reset to match the permissions of the folder (of course, while the service was stopped).
The easiest solution in this case is to detach each database and attach it again (because when attaching the owner is changed to be the service account).