Tailoring surface interactions or grafting of polymers onto surfaces is a versatile tool for controlling wettability, lubrication, adhesion and interactions between surfaces. Using molecular dynamics of a coarse-grained, bead-spring model and dynamic single-chain-in-mean-field simulations, we investigate how structural changes near the surface affect the flow of a polymer melt over the surface and how these changes can be parameterized by a hydrodynamic boundary condition. We study the temperature dependence of the near-surface flow of a polymer melt at a corrugated, attractive surface. At weakly attractive surfaces, lubrication layers form, the slip length is large and increases upon cooling. Close to the glass transition temperature, very large slip lengths are observed. At a more attractive surface, a ‘sticky surface layer’ is build up, giving rise to a small slip length. Upon cooling, the slip length decreases at high temperatures, passes through a minimum and increases upon approaching the glass transition temperature. At strongly attractive surfaces, the Navier slip condition fails to describe Couette and Poiseuille flows simultaneously. A similar failure of the Navier slip condition is observed for the flow of a polymer melt over a brush comprised of identical molecules. The wetting and flow properties of this surface are rather complex. Most notably, the cyclic motion of the grafted molecules gives rise to a reversal of the flow direction at the grafting surface. The failure of the Navier slip condition in both cases can be rationalized within a schematic, two-layer model, which demonstrates that the Navier slip condition fails to simultaneously describe Poiseuille and Couette flow if the fluid at the surface exhibits a higher viscosity than the bulk.