I believe I found the problem. Just because I added songs to a playlist in my library, didn't mean they were actually in the library. Possibly the app was trying to search in the library for song rather than in the playlist. I added each song individually to my library and then to the app and so far no issues. I have closed the app and restarted the device and all the songs were able to be played. Maybe something that Apple Music should fix on their part. Thank you for the help!