Tailoring surface interactions or grafting of polymers onto surfaces is a versatile tool for controlling wettability, lubrication, adhesion, and interactions between surfaces. Many of those properties - e.g., excess free energy and friction at the surface - are dictated by the local structure. Using molecular dynamics simulation of a coarse-grained, bead-spring model, we study the equilibrium structure and near-surface flow of a polymer melt. Two prototypical surfaces are considered: (i) a hard substrate comprised of the first two layers of an FCC solid and (ii) a soft substrate that consists of a polymer brush. We show that the slip length strongly depends on temperature and surface structure. At high temperatures and low grafting densities, we find small slippage. At low temperatures, in the immediate vicinity of the glass transition temperature of the polymer melt, we observe very large slip lengths. At strongly attractive, hard substrates and polymer brushes of intermediate grafting density, we find that the Navier slip condition fails to describe Couette and Poiseuille flows simultaneously. This failure is rationalized within a schematic, two-layer model, which demonstrates that the failure of the Navier slip condition will occur if the fluid at the surface exhibits a higher viscosity than the bulk liquid.