This morning I was trying to add a discussion board to a site that I created with the Publishing with Workflow template. I couldn't seem to find the discussion board web part. I eventually figured it out and below are the steps that I took to do it.

1. Go to Site Actions > Site Settings

2. Site Actions > Manage Site Features

3. Enable Team Collaboration Lists

4. Site Actions > Edit in SharePoint Designer > Lists and Libraries

5. SharePoint List > Discussion Board

Now if you go back to a page and try to add a web part then you should be able to add a discussion board.

Hope this helps someone.